Why it matters: Four to six marks every year: degree and handshake facts, trees, connectivity, planarity, colouring and Euler/Hamilton questions. (Shortest paths and spanning-tree algorithms are in the Algorithms subject.)
c ≥ n − e; forest: e = n − c; connected if e > C(n−1, 2)
Euler
circuit: all degrees even and connected; path: 0 or 2 odd vertices
Planar graph
v − e + f = 2; e ≤ 3v − 6; triangle-free e ≤ 2v − 4
Cayley
labelled trees on n vertices: n^(n−2)
Colouring
ω ≤ χ ≤ Δ + 1; bipartite ⇔ no odd cycle ⇔ χ ≤ 2
König / Gallai
bipartite: ν = τ; always α + τ = n
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Degree sequence / handshake / count edges
Σ deg = 2e; use the parity of odd vertices; Havel–Hakimi for "is this sequence possible".
★★★
Number of components, edges, connectivity bound
Maximum edges without being connected is C(n−1, 2); minimum components is n − e.
★★★
Trees: leaves, height, spanning-tree count
e = n − 1; leaves from the degree sum; Cayley or Kirchhoff for counting.
★★★
Planarity, faces, chromatic number
Euler formula to count faces; e ≤ 3v − 6 to rule out planarity; χ from clique and odd cycles.
★★★
Euler/Hamilton and matching statements
Count odd vertices; Hall's condition; König.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
24 real questions from the official GATE CSE papers (2012 to 2024), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
24 questions · 0 correct of 0 attempted · marks 0 / 37
Year:
GATE 2024 CS2 · Q17MCQ1 mark
Let A be the adjacency matrix of a simple undirected graph G. Suppose A is its own inverse. Which one of the following statements is always TRUE?
GATE 2024 CS1 · Q34NAT1 mark
The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is ______.
GATE 2024 CS1 · Q51MSQ2 marks
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let G be any graph with n vertices and chromatic number k. Which of the following statements is/are always TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q51MSQ2 marks
Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which of the following statements is/are TRUE for every such graph G?
One or more options may be correct. Select all that apply, then submit.
GATE 2022 · Q30NAT1 mark
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ______.
GATE 2022 · Q37MCQ2 marks
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
GATE 2022 · Q52MSQ2 marks
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q16NAT1 mark
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______.
GATE 2020 · Q52NAT2 marks
Graph G is obtained by adding vertex s to K₃,₄ and making s adjacent to every vertex of K₃,₄. The minimum number of colours required to edge-colour G is ______.
GATE 2018 · Q43NAT2 marks
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y + 10z = ______.
GATE 2017 Set 1 · Q20NAT1 mark
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ______.
GATE 2017 Set 2 · Q23NAT1 mark
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 ______.
GATE 2016 Set 2 · Q3NAT1 mark
The minimum number of colours that is sufficient to vertex-colour any planar graph is ______.
GATE 2016 Set 2 · Q28MCQ2 marks
Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements: I. Each compound in U \ S reacts with an odd number of compounds. II. At least one compound in U \ S reacts with an odd number of compounds. III. Each compound in U \ S reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE?
GATE 2014 Set 2 · Q3NAT1 mark
The maximum number of edges in a bipartite graph on 12 vertices is ______.
GATE 2014 Set 1 · Q51NAT2 marks
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) : 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a − c| ≤ 1 and |b − d| ≤ 1. The number of edges in this graph is ______.
GATE 2014 Set 2 · Q51NAT2 marks
A cycle on n vertices is isomorphic to its complement. The value of n is ______.
GATE 2014 Set 3 · Q51MCQ2 marks
If G is a forest with n vertices and k connected components, how many edges does G have?
GATE 2014 Set 1 · Q52MCQ2 marks
An ordered n-tuple (d₁, d₂, …, dₙ) with d₁ ≥ d₂ ≥ … ≥ dₙ is called graphic if there exists a simple undirected graph with n vertices having degrees d₁, d₂, …, dₙ respectively. Which of the following 6-tuples is NOT graphic?
GATE 2014 Set 3 · Q52MCQ2 marks
Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?
GATE 2013 Code A · Q24MCQ1 mark
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
GATE 2013 Code A · Q25MCQ1 mark
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
GATE 2013 Code A · Q26MCQ2 marks
The line graph L(G) of a simple graph G is defined as follows: there is exactly one vertex v(e) in L(G) for each edge e in G; for any two edges e and e' in G, L(G) has an edge between v(e) and v(e') if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
GATE 2012 Code A · Q17MCQ1 mark
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to
Common traps
The handshake formula uses 2e, not e; a self-loop adds 2 to a degree.
Euler ≠ Hamilton: Euler is about edges and has an exact criterion; Hamilton is about vertices and does not.
Passing e ≤ 3v − 6 does not prove a graph is planar, only failing it proves non-planar.
χ(G) ≥ 3 for any odd cycle; a graph with no triangles can still need 3 or more colours (C₅).
A tree on n vertices has n−1 edges and a unique path between any two vertices, and a tree has exactly one spanning tree: itself.