Graph theory is the densest scoring area in Discrete Mathematics, and GATE tests a compact set of ideas that reward understanding over memory: the handshaking lemma, when a graph has an Euler or Hamiltonian circuit, whether it is planar, its chromatic number, and how trees and spanning trees are counted. This set is deliberately about graph structure, not graph algorithms, so if you also want traversal and shortest-path questions, pair it with the Graph Algorithms MCQs. Below are 12 solved MCQs from KnowledgeGate's published question bank, every one a previous-year GATE problem with the year marked. Attempt each before the explanation, which is short on purpose, and follow the inline link to see the full solved page inside the Discrete Mathematics learn module.
Degree and the handshaking lemma
Q1. Which statements are TRUE for undirected graphs? P: the number of odd-degree vertices is even. Q: the sum of degrees of all vertices is even. (GATE 2013, see the solved page)
(a) P only
(b) Q only
(c) Both P and Q
(d) Neither P nor Q
Answer: (c) Both P and Q.
Every edge adds 1 to the degree of two vertices, so the sum of all degrees equals twice the number of edges, which is always even. Even-degree vertices contribute an even amount to that sum, so the odd-degree vertices must together contribute an even amount, forcing their count to be even. This is the handshaking lemma, and both statements are consequences of it.
Q2. Which is TRUE for any simple connected undirected graph with more than 2 vertices? (GATE 2009, see the solved page)
(a) No two vertices have the same degree
(b) At least two vertices have the same degree
(c) At least three vertices have the same degree
(d) All vertices have the same degree
Answer: (b).
In a simple connected graph on n vertices, every degree lies between 1 and n − 1, which is only n − 1 possible values for n vertices. By the pigeonhole principle at least two vertices must share a degree. This is a favourite one-line proof, so recognise the "distinct degrees are impossible" pattern on sight.
Q3. Which graph has an Eulerian circuit? (GATE 2007, see the solved page)
(a) The complement of a cycle on 25 vertices
(b) A complete graph on 90 vertices
(c) Any k-regular graph where k is an even number
(d) None of the above
Answer: (a).
A connected graph has an Eulerian circuit exactly when every vertex has even degree. In the complement of a 25-vertex cycle each vertex has degree 24 − 2 = 22, which is even, and the complement is connected. A complete graph on 90 vertices has every vertex of degree 89 (odd), and option (c) fails because a k-regular graph need not be connected.
Euler and Hamiltonian graphs
Q4. G is a simple undirected graph; some vertices have odd degree. Add a node v adjacent to every odd-degree vertex of G. The resulting graph is sure to be (GATE 2008, see the solved page)
(a) Regular
(b) Complete
(c) Hamiltonian
(d) Euler
Answer: (d) Euler.
Joining v to each odd-degree vertex bumps every one of those odd degrees up by 1, turning them even, while the already-even vertices are untouched. The new vertex v is adjacent to an even number of vertices (the count of odd-degree vertices is even by the handshaking lemma), so v also has even degree. Every vertex now has even degree, which makes the graph Eulerian.
Q5. For an undirected complete graph on n vertices (n > 2), the number of distinct Hamiltonian cycles is (GATE 2019, see the solved page)
(a) n!
(b) (n − 1)!
(c) 1
(d) (n − 1)! / 2
Answer: (d) (n − 1)! / 2.
Fix one vertex to kill the rotational symmetry; the remaining n − 1 vertices can be arranged in (n − 1)! orders. In an undirected graph a cycle and its reverse are the same cycle, so divide by 2. That gives (n − 1)! / 2 distinct Hamiltonian cycles.
Q6. Let G be a simple connected planar graph with 13 vertices and 19 edges. The number of faces in its planar embedding is (GATE 2005, see the solved page)
(a) 6
(b) 8
(c) 9
(d) 13
Answer: (b) 8.
Euler's formula for a connected planar graph is V − E + F = 2. Rearranging, F = 2 − V + E = 2 − 13 + 19 = 8. Remember that this count includes the single unbounded outer face.
Planarity and coloring
Q7. Regarding K4 and Q3 (the 3-cube), which statement is TRUE? (GATE 2011, see the solved page)
(a) K4 is planar while Q3 is not
(b) Both K4 and Q3 are planar
(c) Q3 is planar while K4 is not
(d) Neither K4 nor Q3 is planar
Answer: (b) Both are planar.
K4 (4 vertices, 6 edges) can be drawn as a triangle with the fourth vertex inside connected to the three corners, so it has no crossings. Q3 (8 vertices, 12 edges) is the cube graph, which can also be redrawn in the plane without crossings, as a small square nested inside a larger one. Neither contains a K5 or K3,3 subdivision, so both stay planar.
Q8. Let G be the non-planar graph with the minimum possible number of edges. Then G has (GATE 2007, see the solved page)
(a) 10 edges and 6 vertices
(b) 10 edges and 5 vertices
(c) 9 edges and 6 vertices
(d) 9 edges and 5 vertices
Answer: (c) 9 edges and 6 vertices.
By Kuratowski's theorem, the two minimal non-planar graphs are K5 (10 edges) and K3,3 (9 edges). K3,3 is the cheaper of the two, and it has 6 vertices and 9 edges. So the fewest edges any non-planar graph can have is 9, realised by K3,3.
Q9. The chromatic number of an n-vertex simple connected graph (n ≥ 2) with no odd-length cycle is (GATE 2009, see the solved page)
(a) n − 1
(b) 3
(c) 2
(d) n
Answer: (c) 2.
A graph has no odd cycle if and only if it is bipartite, meaning its vertices split into two independent sets. Two colours, one per side, suffice and are necessary because the graph has at least one edge. So the chromatic number is exactly 2.
Q10. The minimum number of colours to properly colour the vertices of a cycle with n nodes is (GATE 2002, see the solved page)
(a) 2
(b) 3
(c) 4
(d) n − 2⌊n/2⌋ + 2
Answer: (d) n − 2⌊n/2⌋ + 2.
For an even cycle two colours alternate cleanly, but for an odd cycle the last vertex clashes with the first, so a third colour is needed. The expression n − 2⌊n/2⌋ equals 0 for even n and 1 for odd n, so adding 2 gives exactly 2 for even cycles and 3 for odd cycles, which is the correct chromatic number of C_n.
Trees and spanning trees
Q11. If G is a forest with n vertices and k connected components, how many edges does it have? (GATE 2014, see the solved page)
(a) ⌊n/k⌋
(b) ⌈n/k⌉
(c) n − k
(d) n − k + 1
Answer: (c) n − k.
A forest is a disjoint union of trees, and a tree on m vertices has m − 1 edges. If the k components have v1, ..., vk vertices summing to n, the total edge count is (v1 − 1) + ... + (vk − 1) = n − k. As a check, a single tree (k = 1) gives the familiar n − 1 edges.
Q12. What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees? (GATE 2007, see the solved page)
(a) 1
(b) 2
(c) 3
(d) n
Answer: (c) 3.
A connected graph with n vertices and n edges has exactly one cycle, because the number of independent cycles is E − V + 1 = 1. Every spanning tree keeps all the non-cycle edges and drops exactly one edge of that cycle, so the number of spanning trees equals the cycle length. A simple cycle has length at least 3, so every such graph is guaranteed at least 3 spanning trees.
Where these 12 fit in your preparation
The set tracks the real subtopic map: degree and the handshaking lemma (Q1-Q3), Euler and Hamiltonian conditions (Q4-Q5), Euler's formula and planarity (Q6-Q8), coloring (Q9-Q10), and trees and spanning trees (Q11-Q12). Most of these reduce to one or two counting identities, so if you missed several, drill the handshaking lemma and Euler's formula until they are automatic.
Rebuild any weak spot in the Discrete Mathematics learn module, then round out the subject with the Propositional and Predicate Logic MCQs. The full GATE sequence lives inside GATE Guidance by Sanchit Sir, and the GATE CS category page shows how graph theory sits in the wider syllabus. Solve, review the misses, and come back a week later for the second pass.
