Register

Web Page

Syllabus: Connectivity, Matching, Coloring.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}& \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} & 1&1&0&0&1&1&0&1&0&1&0&0.6&1
\\\hline\textbf{2 Marks Count} & 3 &1&0&1&1&1&0&0&0&0&0&0.7&3
\\\hline\textbf{Total Marks} & 7 &3&0&2&3&3&0&1&0&1&\bf{0}&\bf{2}&\bf{7}\\\hline
\end{array}}}$$

Filter

Recent questions in Graph Theory

16 votes
2 answers
844
CMI2015-A-05
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What is the degree of vertex $10$ ? $5$ $6$ $7$ $8$
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What ...
User Avatar
0 votes
2 answers
847
Bipartite Graph
Consider the graph given below: The two distinct sets of vertices, which make the graph bipartite are: (A) (v1, v4, v6); (v2, v3, v5, v7, v8) (B) (v1, v7, v8); (v2, v3, v5, v6) (C) (v1, v4, v6, v7); (v2, v3, v5, v8) (D) (v1, v4, v6, v7, v8); (v2, v3, v5)
Consider the graph given below: The two distinct sets of vertices, which make the graph bipartite are:(A) (v1, v4, v6); (v2, v3, v5, v7, v8)(B) (v1, v7, v8); (v2, v3, v5,...
User Avatar
1 votes
4 answers
848
CMI2013-B-03
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least two vertices with the same degree.
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least...
User Avatar
11 votes
1 answer
851
CMI2012-B-01
Let $G=(V, E)$ be a graph where $\mid V \mid =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Consider a path of maximum length in $G$.)
Let $G=(V, E)$ be a graph where $\mid V \mid =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Cons...
User Avatar
4 votes
2 answers
852
CMI2012-A-02
Let $T$ be a tree on 100 vertices. Let $n_i$ be the number of vertices in $T$ which have exactly $i$ neighbors. Let $s= \Sigma_{i=1}^{100} i . n_i$ Which of the following is true? $s=99$ $s=198$ $99 \: < \: s \: < \: 198$ None of the above
Let $T$ be a tree on 100 vertices. Let $n_i$ be the number of vertices in $T$ which have exactly $i$ neighbors. Let $s= \Sigma_{i=1}^{100} i . n_i$ Which of the following...
User Avatar
2 votes
2 answers
857
CMI2010-B-02
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1, \dots , v_k$ such that for $0 \leq i < k,$ $v_i$ is connected to $v_{i+1}$ in $G$.
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1...
User Avatar
4 votes
1 answer
858
ISRO-2013-76
The number of edges in a 'n' vertex complete graph is? $n ^{*} (n - 1) / 2$ $n^{2}$ $n ^{*} (n + 1) / 2$ $n ^{*} (n + 1)$
The number of edges in a 'n' vertex complete graph is?$n ^{*} (n - 1) / 2$$n^{2}$$n ^{*} (n + 1) / 2$$n ^{*} (n + 1)$
User Avatar
0 votes
2 answers
859
vertex cover
39. A _________ complete subgraph and a _________ subset of vertices of a graph $G = (V, E)$ are a clique and a vertex cover respectively. (A) minimal, maximal (B) minimal, minimal (C) maximal, maximal (D) maximal, minimal
39.A _________ complete subgraph and a _________ subset of vertices of a graph $G = (V, E)$ are a clique and a vertex cover respectively.(A) minimal, maximal(B) minimal, ...
User Avatar
2 votes
1 answer
860
UGC NET CSE | June 2013 | Part 2 | Question: 38
How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components? M+N-C M-N-C M-N+C M+N+C
How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components?M+N-CM-N-CM-N+CM+N+C
User Avatar
Page: