Graph Theory Questions in GATE CSE: Patterns and Formulas

Graph theory in GATE CSE is a counting subject, not a drawing subject. Almost every past question reduces to one of six families: degree and edge counting, trees and spanning trees, planarity through Euler's formula, colouring, matching, and connectivity. This guide names each family, gives the formula that carries it, and works one short example.

Key takeaways

• The official syllabus line is short: "Graphs: connectivity, matching, colouring", inside the Discrete Mathematics part of Engineering Mathematics.
• Degree and edge counting combined with Euler's formula is the highest scoring graph concept in the book's model, at 88.5 out of 100.
• Nearly every graph question is a numeric answer type worth 1 or 2 marks, so there is no negative marking on an attempt.
• Recent papers combine two constraints in one question, for example planarity plus a face length, or colouring plus an edge count.
• Matching is the one syllabus-named graph topic with a thin record and a real due signal.

Where graph theory sits in the paper

The official GATE 2027 pattern page allots about 13 marks to Engineering Mathematics. Graph theory is one slice of the Discrete Mathematics half of that section. Third-party analyst compilations that separate the two halves, covering 2016 to 2026, report Discrete Mathematics between 3 and 12 marks with a median near 6 or 7. Those figures are approximate and differ by about 2 to 3 marks between sources, because analysts disagree about where a graph question belongs.

The practical reading: expect one or two graph items in a shift, worth 1 to 3 marks together, on a topic you can finish in under three minutes if you know the formula. For the wider picture of how the mathematics section is built, see Engineering Mathematics important topics and the broader Discrete Mathematics guide.

The six families at a glance

Years are an analyst reconstruction from public question archives and are approximate. Scores are model based analytical confidence values on a 0 to 100 scale, not probabilities that a question will appear.

Family 1: degree and edge counting

Everything here comes from one identity: the sum of all vertex degrees equals twice the number of edges. Consequences worth memorising are that the number of odd-degree vertices is always even, that a k-regular graph on n vertices has nk/2 edges and exists only when nk is even, and that a degree sequence whose sum is odd is impossible.

A typical shape: a simple graph has 12 edges, three vertices of degree 5, and every remaining vertex of degree 3. How many vertices does it have? The degree sum is 24. The three high-degree vertices contribute 15, leaving 9, which is three vertices of degree 3. The answer is 6.

The same identity handles trees. In a tree on n vertices the edge count is fixed at n minus 1, so the degree sum is 2(n − 1), and leaf counts follow from the internal degrees.

Family 2: trees and spanning trees

Three counting formulas cover most of what has been asked:

• The complete graph K(n) has n^(n−2) labelled spanning trees, which is Cayley's formula.
• The complete bipartite graph K(m, n) has m^(n−1) times n^(m−1) spanning trees.
• The cycle C(n) has exactly n spanning trees, one for each edge you delete.

For example, K(2, 3) has 2^2 times 3^1, which is 12 spanning trees. Small cases like this are what the paper actually asks, because the answer has to be typed in.

The definitional trap matters as much as the formulas. A tree is connected, acyclic and has n minus 1 edges, and any two of those three imply the third. A graph with n minus 1 edges alone is not a tree, and past distractors have been built on exactly that confusion.

This guide gives one example per family. The book scores all 25 Engineering Mathematics concepts on the same eight-factor model and pairs each graph family with practice questions built around its recurring variants.

Family 3: planarity and Euler's formula

For a connected planar simple graph, v − e + f = 2, where f counts the outer face. Two bounds follow: e is at most 3v − 6 for v at least 3, and e is at most 2v − 4 when the graph is bipartite or triangle free. If every face is bounded by exactly g edges, then g·f = 2e, which pins down the remaining unknown.

Worked example: a connected planar simple graph has 10 vertices and every face is bounded by exactly 4 edges. How many edges? From 4f = 2e we get f = e/2. Substituting into Euler's formula, 10 − e + e/2 = 2, so e = 16. It sits exactly on the bipartite bound of 2v − 4, which is a useful sanity check.

The classic slip is applying e ≤ 3v − 6 to a triangle-free graph. Recent papers favour exactly this combined-constraint shape, mixing planarity with a face length or a degree condition in one numeric answer.

Family 4: colouring

Chromatic numbers of standard graphs are worth knowing cold: the cycle C(n) needs 2 colours when n is even and 3 when n is odd; the complete graph K(n) needs n; a wheel needs 3 for an even rim and 4 for an odd rim; a graph is bipartite exactly when its chromatic number is at most 2, which happens exactly when it has no odd cycle. Every planar graph needs at most 4.

Bounds fill the gaps: the clique number is a lower bound, and one more than the maximum degree is an upper bound. So a wheel built on a 7-vertex rim needs 3 colours for the odd rim plus one more for the hub, which is 4.

Harder variants ask for the chromatic number of a complement, or of a complete graph with a perfect matching removed. Those need a small clique-cover argument rather than a formula.

Family 5: matching, and Family 6: connectivity

Matching has the thinnest record of any syllabus-named graph topic, but it is cheap. The number of perfect matchings of K(2n) is the double factorial (2n − 1)!!, so K(6) has 5 × 3 × 1 = 15. The number of perfect matchings of K(n, n) is n factorial. The common wrong answer treats the first count as (2n)!/2.

Connectivity questions are extremal counts. The maximum number of edges in a disconnected simple graph on n vertices is C(n − 1, 2), so on 8 vertices it is 21. A simple graph is guaranteed connected if every degree is at least n/2, or if the edge count exceeds C(n − 1, 2). The chain vertex connectivity at most edge connectivity at most minimum degree is the source of most multiple-select statements here.

The traps that repeat

The same list, alongside the traps of every other subject, is collected in the common mistakes guide, and the formulas above appear in the GATE CSE formula sheet.

How to practise this

Do not read graph theory; compute it. Take each of the six families and write the formula from memory, then build two instances of your own and check them against the formula. The rewarding part is that the instances in the paper are small, with 5 to 10 vertices, because the answer has to be entered as a number.

Then do a mixed set where you cannot see which family a question belongs to, because recognising the family is the actual skill under exam pressure. Pair this with the most repeated topics list so that graph theory gets the share of your revision time its weight deserves, and no more.