Graph theory is where Discrete Mathematics gets dense with named theorems, and they split into two worlds. The structural side is degrees, Euler and Hamiltonian tours, planarity, coloring, connectivity and trees: the definitions and theorems GATE tests directly. The algorithmic side, traversal and shortest paths, is a separate skill that builds on this one.
Almost every question here is one clean theorem applied carefully, so the counting facts and the named conditions have to be exact. Several of them are stated in terms of degrees, so start there.
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.
Connectivity, cut vertices and bridges
A graph is connected if some path joins every pair of vertices; otherwise it breaks into connected components. Two refinements carry most of the marks. A cut vertex is a vertex whose removal increases the number of components, and a bridge is an edge whose removal does the same. The quick test for a bridge: an edge is a bridge if and only if it lies on no cycle.
How strongly a graph holds together is measured two ways. Vertex connectivity, kappa of G, is the fewest vertices you must delete to disconnect it; edge connectivity, lambda of G, is the fewest edges. Whitney's inequality ties both to the smallest degree: kappa of G is at most lambda of G, which is at most the minimum degree.
Check it on two triangles glued at a shared vertex. The shared vertex has degree 4 and the other four have degree 2, so the minimum degree is 2. Deleting the shared vertex splits the graph, so kappa is 1; every edge lies on a triangle, so no single edge deletion disconnects it and lambda is 2. That reads 1, 2, 2, with the first step strict. A connected graph on n vertices also needs at least n minus 1 edges, and the graphs sitting exactly on that floor are the trees.
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 questions on this topic come in a small set of recognisable shapes: a degree-sequence feasibility check, an Euler-versus-Hamiltonian identification, a planarity or Euler-formula count, a chromatic-number problem, a cut-vertex or connectivity question, and a spanning-tree count. Each one is short, which is exactly why precise recall of every condition pays off. There is no time to re-derive a theorem in the hall.
Once you can reason about connectivity and trees, traversal and shortest-path algorithms build straight on top of them, and the graph algorithms deep-dive on BFS, DFS and shortest paths carries on from there. To drill the structural theorems, work the Euler and Hamiltonian practice set and the graph coloring set from previous years.
Practise it, do not just read it
Graph theory rewards exact recall, not improvisation. Learn handshaking, the two Euler conditions, Euler's formula, the chromatic values, the connectivity inequality 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.
