Graph theory is the densest topic in the Discrete Mathematics question bank, and it splits cleanly into two worlds. One is the structural mathematics of graphs, degrees, Euler and Hamiltonian tours, planarity, coloring and trees. The other is the algorithmic side, traversal and shortest paths, which we cover separately. This post is the first world, the definitions and theorems that GATE tests directly.
Get the counting facts and the named conditions exact, because most questions here are one clean theorem applied carefully. Let us build it up.
Degree and the handshaking lemma
The degree of a vertex is the number of edges incident on it. The single most useful fact in the whole topic is the handshaking lemma: the sum of all vertex degrees equals twice the number of edges, because every edge contributes to exactly two endpoints.
Sum of degrees equals 2 times the number of edges.
An immediate corollary the exam loves: the number of vertices of odd degree is always even. If a question gives you a degree sequence and asks whether such a graph can exist, count the odd entries first. A graph with vertices of degrees 3, 3, 2, 2 has two odd-degree vertices, an even count, and total degree 10, so it could have 5 edges.
Euler paths versus Hamiltonian paths
These two are constantly confused, and telling them apart is half the marks in this topic.
An Euler path traverses every edge exactly once. An Euler circuit does the same and returns to the start. The conditions are clean and worth memorising for a connected graph:
An Euler circuit exists if and only if every vertex has even degree.
An Euler path that is not a circuit exists if and only if exactly two vertices have odd degree, and the path must start at one and end at the other.
A Hamiltonian path visits every vertex exactly once; a Hamiltonian circuit returns to the start. The contrast that matters: there is no simple necessary-and-sufficient condition for a Hamiltonian circuit, and deciding whether one exists is an NP-complete problem. There is a sufficient condition, Dirac's theorem: if a simple graph has n vertices with n at least 3, and every vertex has degree at least n divided by 2, then it has a Hamiltonian circuit. Sufficient, not necessary, so its failure proves nothing.
One line to hold: Euler is about edges and has an easy degree test; Hamiltonian is about vertices and is genuinely hard.
Planar graphs and Euler's formula
A graph is planar if it can be drawn in the plane with no edges crossing. For any connected planar graph drawn this way, Euler's formula relates vertices, edges and faces:
Vertices minus edges plus faces equals 2.
From it comes a bound for a simple connected planar graph with at least 3 vertices: the number of edges is at most 3 times vertices minus 6. This is a fast non-planarity test. The complete graph on 5 vertices has 10 edges but 3 times 5 minus 6 is 9, so it exceeds the bound and cannot be planar. The complete bipartite graph on 3 plus 3 vertices fails a tighter bipartite bound and is also non-planar. Kuratowski's theorem makes this exact: a graph is planar if and only if it contains no subdivision of those two graphs.
Graph coloring and the chromatic number
A proper vertex coloring assigns colors so that no two adjacent vertices share one. The chromatic number, written chi of G, is the fewest colors needed. Key values to know:
A complete graph on n vertices needs n colors, since every pair is adjacent.
A bipartite graph, and any graph with no odd cycle, needs just 2 colors.
A cycle needs 2 colors if its length is even and 3 if it is odd.
These standard chromatic numbers are worth holding ready:
Graph | Chromatic number |
|---|---|
Complete graph on n vertices | n |
Bipartite graph (no odd cycle) | 2 |
Cycle of even length | 2 |
Cycle of odd length | 3 |
Any tree with an edge | 2 |
The famous result is the four color theorem: every planar graph can be properly colored with at most 4 colors. Chromatic-number questions usually reduce to spotting whether the graph is bipartite, complete, or an odd cycle.
Trees and counting spanning trees
A tree is a connected acyclic graph. Its defining count: a tree on n vertices has exactly n minus 1 edges, and adding any edge creates exactly one cycle while removing any edge disconnects it. A spanning tree of a connected graph is a subgraph that is a tree and includes every vertex.
The counting result GATE tests is Cayley's formula: the number of distinct labelled spanning trees of a complete graph on n vertices is n raised to the power n minus 2. For the complete graph on 4 vertices that is 4 to the power 2, which is 16 spanning trees. Work that number by hand once so the formula sticks, because the exam gives you n and expects the count immediately.
How graph theory is tested in GATE
GATE CS pulls from this topic every year. Expect a handshaking or degree-sequence question, an Euler-versus-Hamiltonian identification, a planarity or Euler-formula count, a chromatic-number problem, and a spanning-tree count. They are individually short, which is exactly why precise recall of each condition pays off, there is no time to re-derive.
This structural side pairs with the algorithmic side of graphs. Once you can reason about connectivity and trees, traversal and shortest-path algorithms build directly on them, which our graph algorithms deep-dive on BFS, DFS and shortest paths picks up. To drill the structural theorems, use the Euler and Hamiltonian practice set and the graph coloring set from previous years.
Practise it, do not just read it
Graph theory is confirmed on questions. Learn handshaking, the two Euler conditions, Euler's formula, the chromatic values and Cayley's formula, then solve until each one is reflex.
Work the previous-year Euler and Hamiltonian practice set and graph coloring set with worked solutions.
For Discrete Mathematics across the whole GATE CS syllabus, GATE Guidance by Sanchit Sir sequences graph theory with logic, set theory and relations.
Browse the neighbouring topics in the CS Fundamentals category.
Learn the named conditions cold, keep Euler and Hamiltonian cleanly apart, and hand-count one set of spanning trees. Do that, and graph theory becomes the most reliable source of marks in Discrete Mathematics.
