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}}}$$

Previous GATE Questions in Graph Theory

1 votes
2 answers
2
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.
19 votes
5 answers
5
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .
13 votes
5 answers
9
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
28 votes
6 answers
11
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is...
32 votes
14 answers
12
Let $G$ be an undirected complete graph on $n$ vertices, where $n 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to$n!$$(n-1)!$$1$$\frac{(n-1)!}{2}...
32 votes
5 answers
14
44 votes
9 answers
15
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
7 votes
3 answers
16
1 votes
0 answers
17
15 votes
4 answers
18
31 votes
4 answers
19
To see more, click for the full list of questions or popular tags.