Graph Theory — Trees, Paths & Connectivity
Complete Guide for GATE CS — Graph Types, Degree Sequence, Euler & Hamiltonian Paths, Trees, Spanning Trees, Planarity & Coloring
Last Updated: April 2026
📌 Key Takeaways
- Handshaking Lemma: Sum of all vertex degrees = 2|E|. Every graph has an even number of odd-degree vertices.
- Tree: Connected, acyclic graph with n vertices and exactly n−1 edges. Adding any edge creates exactly one cycle; removing any edge disconnects it.
- Euler circuit/path: Visits every edge exactly once. Circuit exists ↔ all vertices have even degree. Path exists ↔ exactly 2 vertices have odd degree.
- Hamiltonian path/circuit: Visits every vertex exactly once. No simple polynomial test exists — NP-complete in general.
- Planarity (Euler’s formula): V − E + F = 2 for connected planar graphs. Bound: E ≤ 3V−6. K₅ and K₃,₃ are not planar (Kuratowski’s theorem).
- Graph coloring: Chromatic number χ(G) = minimum colors to color vertices so no two adjacent vertices share a color. For bipartite graphs, χ = 2 (or 1 if edgeless).
- GATE CS tests graph theory heavily — expect 1–2 questions on trees, Euler paths, planarity, or chromatic number every year.
1. Graph Basics — Types & Terminology
A graph G = (V, E) consists of a set V of vertices (or nodes) and a set E of edges (pairs of vertices). Graphs model relationships between objects — networks, dependencies, maps, and more.
| Graph Type | Description | Example |
|---|---|---|
| Simple Graph | No self-loops; no multiple edges between same pair | Friendship network |
| Multigraph | Multiple edges allowed between same vertices | Roads between cities |
| Directed Graph (Digraph) | Edges have direction: (u, v) ≠ (v, u) | Web page links |
| Undirected Graph | Edges have no direction: {u, v} = {v, u} | Social network friendships |
| Weighted Graph | Each edge has an associated weight/cost | Road map with distances |
| Complete Graph Kn | Every pair of vertices is connected by an edge | K₄ has 6 edges |
| Bipartite Graph | Vertices split into two sets; edges only between sets | Job-applicant matching |
| Regular Graph | Every vertex has the same degree | Kn is (n−1)-regular |
Complete Graph Kn — Key Formulas
Edges in Kn: |E| = n(n−1)/2
Degree of each vertex: n−1 (connected to every other vertex)
Complete Bipartite Graph Km,n edges: m × n
K₅: 5 vertices, 10 edges; K₃,₃: 6 vertices, 9 edges
2. Degree Sequence & Handshaking Lemma
The degree of a vertex v, written deg(v), is the number of edges incident to v. Self-loops count twice. In a directed graph, each vertex has an in-degree (edges coming in) and out-degree (edges going out).
Handshaking Lemma
∑ deg(v) = 2|E| (for undirected graphs)
∑ in-deg(v) = ∑ out-deg(v) = |E| (for directed graphs)
Corollary: The number of odd-degree vertices in any graph is always even.
Reason: 2|E| is even. Sum of even-degree vertices is even. So sum of odd-degree vertices must also be even → their count is even.
2.1 Degree Sequence
The degree sequence of a graph is the list of vertex degrees arranged in non-increasing order. Not every sequence is graphical (realizable as a simple graph). Use Erdős–Gallai theorem to check: sequence d₁ ≥ d₂ ≥ … ≥ dₙ is graphical if and only if:
- ∑di is even, AND
- For each k from 1 to n: ∑i=1k di ≤ k(k−1) + ∑i=k+1n min(di, k)
3. Paths, Walks & Connectivity
| Term | Definition |
|---|---|
| Walk | Sequence of vertices where consecutive vertices are adjacent; edges and vertices can repeat |
| Trail | Walk with no repeated edges (vertices may repeat) |
| Path | Walk with no repeated vertices (and thus no repeated edges) |
| Circuit / Closed Walk | Walk that starts and ends at the same vertex |
| Cycle | Closed path — no repeated vertices except start=end |
| Connected Graph | A path exists between every pair of vertices |
| Connected Component | A maximal connected subgraph |
Connectivity in Directed Graphs
Weakly connected: Underlying undirected graph is connected
Strongly connected: Path exists from u to v AND from v to u for every pair (u,v)
Strongly Connected Component (SCC): Maximal strongly connected subgraph (found using Kosaraju’s or Tarjan’s algorithm)
4. Euler & Hamiltonian Paths
| Euler Path/Circuit | Hamiltonian Path/Circuit | |
|---|---|---|
| Visits | Every EDGE exactly once | Every VERTEX exactly once |
| Circuit condition | All vertices have even degree | No simple polynomial condition (NP-complete) |
| Path condition | Exactly 2 vertices have odd degree (they are endpoints) | No simple polynomial condition |
| Connectivity required | Yes (ignore isolated vertices) | Yes |
| Algorithm | Fleury’s or Hierholzer’s (O(E)) | No polynomial algorithm known |
Euler Path/Circuit — Decision Rules
Euler Circuit exists ↔ Graph is connected AND every vertex has even degree
Euler Path (not circuit) exists ↔ Graph is connected AND exactly 2 vertices have odd degree (these become the start and end)
No Euler path exists if more than 2 vertices have odd degree
The famous Königsberg Bridge Problem: 4 vertices all had odd degree → no Euler path possible.
5. Trees — Properties & Types
A tree is a connected, acyclic (undirected) graph. All of the following are equivalent for a graph with n vertices:
- G is a tree
- G is connected with n−1 edges
- G is acyclic with n−1 edges
- Any two vertices are connected by exactly one path
- G is connected, but removing any edge disconnects it (minimally connected)
- G is acyclic, but adding any edge creates exactly one cycle (maximally acyclic)
Tree Formulas
Edges in a tree: |E| = n − 1
Labeled trees on n vertices: nn−2 (Cayley’s formula)
K₁: 1 tree, K₂: 1 tree, K₃: 3 trees, K₄: 16 trees (= 44−2 = 16 ✓)
A forest (acyclic, possibly disconnected) with n vertices and k connected components has n − k edges.
5.1 Rooted Trees
| Type | Definition |
|---|---|
| Rooted Tree | One vertex designated as root; all edges directed away from root |
| Binary Tree | Each node has at most 2 children (left, right) |
| Full Binary Tree | Every node has 0 or 2 children |
| Complete Binary Tree | All levels full except possibly last; last level filled left-to-right |
| Perfect Binary Tree | All leaves at same depth; internal nodes have exactly 2 children |
Binary Tree Formulas
Perfect binary tree of height h: 2h+1−1 nodes; 2h leaves
Full binary tree: If i = internal nodes, then leaves = i + 1
Height of complete binary tree with n nodes: ⌊log₂ n⌋
6. Spanning Trees
A spanning tree of a connected graph G is a subgraph that is a tree AND includes all vertices of G. It has exactly n−1 edges (where n = |V|).
6.1 Number of Spanning Trees
For a complete graph Kn, the number of spanning trees = nn−2 (Cayley’s formula). For other graphs, use the Matrix-Tree Theorem (Kirchhoff’s theorem): the number of spanning trees equals any cofactor of the Laplacian matrix L = D − A, where D is the degree matrix and A is the adjacency matrix.
6.2 Minimum Spanning Tree (MST)
The MST of a weighted connected graph is the spanning tree with minimum total edge weight. Two key algorithms:
| Prim’s Algorithm | Kruskal’s Algorithm | |
|---|---|---|
| Approach | Grow MST vertex by vertex (greedy, similar to Dijkstra) | Sort all edges by weight; add edge if no cycle |
| Data Structure | Priority queue (min-heap) | Union-Find (Disjoint Set Union) |
| Time Complexity | O(E log V) with binary heap | O(E log E) = O(E log V) |
| Best for | Dense graphs | Sparse graphs |
MST Cut Property
For any cut (partition of V into two sets S and V−S), the minimum-weight edge crossing the cut is always in some MST.
Cycle Property: The maximum-weight edge in any cycle is never in any MST (assuming distinct weights).
7. Planarity & Euler’s Formula
A graph is planar if it can be drawn in a plane without any edges crossing. Such a drawing is called a planar embedding.
Euler’s Planar Graph Formula
For any connected planar graph: V − E + F = 2
Where V = vertices, E = edges, F = faces (regions, including the outer unbounded face)
Bound for simple planar graphs: E ≤ 3V − 6 (for V ≥ 3)
Bound if no triangles (girth ≥ 4): E ≤ 2V − 4
If E > 3V−6 for any graph, it CANNOT be planar.
7.1 Non-Planar Graphs — Kuratowski’s Theorem
A graph is non-planar if and only if it contains a subdivision of K₅ or K₃,₃ as a subgraph.
| Graph | V | E | 3V−6 | E > 3V−6? | Planar? |
|---|---|---|---|---|---|
| K₄ | 4 | 6 | 6 | No (E=3V−6) | Yes ✓ |
| K₅ | 5 | 10 | 9 | Yes (10 > 9) | No ✗ |
| K₃,₃ | 6 | 9 | 12 | No (need girth≥4 bound: 2V−4=8, 9>8) | No ✗ |
| Petersen Graph | 10 | 15 | 24 | No | No ✗ (contains K₃,₃ subdivision) |
8. Graph Coloring & Chromatic Number
A proper vertex coloring assigns a color to each vertex such that no two adjacent vertices share the same color. The chromatic number χ(G) is the minimum number of colors needed.
| Graph | χ(G) | Reason |
|---|---|---|
| Empty graph (no edges) | 1 | All vertices can share one color |
| Bipartite graph (non-empty) | 2 | Two sets, edges only between sets |
| Odd cycle C2k+1 | 3 | Odd cycles require 3 colors |
| Even cycle C2k | 2 | Bipartite |
| Complete graph Kn | n | All vertices adjacent to each other |
| Planar graph | ≤ 4 | Four Color Theorem |
| Tree | 2 (if non-trivial) | Trees are bipartite |
Chromatic Number Bounds
Lower bound: χ(G) ≥ ω(G) (ω = clique number — size of largest complete subgraph)
Upper bound: χ(G) ≤ Δ(G) + 1 (Δ = maximum degree; Brooks’ theorem gives χ ≤ Δ except for Kn and odd cycles)
Four Color Theorem: Every planar graph has χ(G) ≤ 4
9. Worked Examples (GATE CS Level)
Example 1 — Degree Sequence & Handshaking
Problem: (a) A simple graph has 7 vertices with degrees 1, 2, 2, 3, 3, 4, d. Find d and the number of edges. (b) Is the sequence (3, 3, 3, 3) graphical (realizable as a simple graph)? (c) How many edges does K₈ have?
(a) Finding d and edge count:
By Handshaking Lemma: ∑deg(v) = 2|E| → sum must be even.
Current sum: 1+2+2+3+3+4+d = 15+d. For this to be even, d must be odd.
Since it is a simple graph with 7 vertices, max degree = 6. So d ∈ {1, 3, 5}.
Typically in GATE problems, the context determines d. Most common: d = 3.
If d = 3: Total degree = 15+3 = 18. |E| = 18/2 = 9 edges
(b) Is (3,3,3,3) graphical?
Step 1: ∑di = 12, which is even ✓
Step 2 (Erdős–Gallai for k=1): 3 ≤ 1×0 + min(3,1)+min(3,1)+min(3,1) = 0+1+1+1 = 3 ✓
Yes — this sequence is graphical. It is realized by the complete graph K₄ (4 vertices, each connected to the other 3).
Degree sequence (3,3,3,3) is realized by K₄. Yes, it is graphical.
(c) Edges in K₈:
|E(K₈)| = 8(8−1)/2 = 8×7/2 = 28 edges
Example 2 — Trees & Spanning Trees
Problem: (a) A forest with 12 vertices has 4 connected components. How many edges does it have? (b) How many labeled spanning trees does K₄ have? (c) A tree has 5 vertices of degree 1, 2 vertices of degree 2, and some vertices of degree 3. How many vertices of degree 3 are there?
(a) Forest with 12 vertices, 4 components:
A forest with n vertices and k components has n−k edges.
|E| = 12 − 4 = 8 edges
(b) Labeled spanning trees of K₄:
By Cayley’s formula: nn−2 = 44−2 = 4² = 16 spanning trees
(c) Degree-3 vertices in the tree:
Let x = number of degree-3 vertices. Total vertices n = 5 + 2 + x = 7 + x.
For a tree: |E| = n − 1 = 6 + x
By Handshaking Lemma: ∑deg = 2|E|
∑deg = 5×1 + 2×2 + x×3 = 5 + 4 + 3x = 9 + 3x
So: 9 + 3x = 2(6 + x) = 12 + 2x
3x − 2x = 12 − 9 → x = 3
Degree-3 vertices = 3. Total vertices = 10. Edges = 9. (Verify: 5×1+2×2+3×3 = 5+4+9 = 18 = 2×9 ✓)
Example 3 — Planarity & Chromatic Number
Problem: (a) A connected planar graph has 10 vertices and 15 edges. How many faces does it have? (b) Is a graph with 6 vertices and 12 edges necessarily non-planar? (c) What is χ(C₇)? What is χ(K₃,₄)?
(a) Faces using Euler’s formula:
V − E + F = 2 → 10 − 15 + F = 2
F = 2 − 10 + 15 = 7 faces
(b) Graph with V=6, E=12 — planar?
Check bound: 3V − 6 = 3(6) − 6 = 12. The condition for non-planarity is E > 3V−6.
Here E = 12 = 3V−6, so the bound is NOT violated. This graph could be planar — the bound is only a sufficient condition for non-planarity, not a necessary one.
E = 3V−6 means we cannot conclude non-planarity from this bound alone. Not necessarily non-planar.
Note: K₃,₃ has V=6, E=9, and is non-planar despite E < 3V−6 = 12.
(c) Chromatic numbers:
χ(C₇): C₇ is an odd cycle (7 vertices). Odd cycles always require 3 colors (you can’t 2-color them because the last vertex is adjacent to the first, and both forced the same color).
χ(C₇) = 3 (odd cycles need 3 colors)
χ(K₃,₄): K₃,₄ is a complete bipartite graph. All bipartite graphs (with at least one edge) are 2-colorable — assign one color to each partition.
χ(K₃,₄) = 2 (all bipartite graphs have chromatic number 2)
10. 5 Common Mistakes in Graph Theory
Mistake 1 — Confusing Euler Path with Hamiltonian Path
What happens: Students apply Euler’s condition (degree parity) to Hamiltonian problems, or try to use Hamiltonicity for “visit all edges” problems.
Root cause: Both sound like “visit everything once” but refer to completely different objects (edges vs vertices).
Correct approach: Euler = Edges. Hamiltonian = Vertices (H for H). Euler has a clean O(1) test; Hamiltonian is NP-complete.
Mistake 2 — Forgetting the Outer Face in Euler’s Formula
What happens: Students count interior faces only and get F wrong, leading to incorrect vertex/edge counts.
Root cause: The formula V − E + F = 2 counts the unbounded outer region as one face.
Correct approach: Always add 1 for the outer/infinite face. For a tree: 1 face (just the outer region); V−(V−1)+1 = 2 ✓.
Mistake 3 — Misusing E ≤ 3V−6 for Bipartite Graphs
What happens: Students use E ≤ 3V−6 to check planarity for K₃,₃ (V=6, E=9, 3V−6=12 → 9 ≤ 12 ✓) and wrongly conclude K₃,₃ is planar.
Root cause: The bound E ≤ 3V−6 assumes the graph may contain triangles (3-cycles). Bipartite graphs have girth ≥ 4, so the tighter bound E ≤ 2V−4 applies.
Correct approach: For bipartite graphs, use E ≤ 2V−4. K₃,₃: E=9 > 2(6)−4=8 → non-planar ✓.
Mistake 4 — Claiming a Non-Graphical Degree Sequence is Valid
What happens: Students accept (5, 3, 3, 2, 1) as a valid graph without checking, then contradict themselves in the problem.
Root cause: Not checking the two quick tests: sum must be even, and max degree must be < n (for simple graphs).
Correct approach: First check: ∑di is even. Second: max degree < n. Then apply Erdős–Gallai if needed. Example: (5,3,3,2,1) — sum=14 (even ✓), but max degree=5=n → invalid for simple graph.
Mistake 5 — Saying χ(G) = ω(G) Always
What happens: Students think the chromatic number always equals the clique number (size of largest complete subgraph).
Root cause: While ω(G) is always a lower bound for χ(G), they can differ. The Mycielski construction gives triangle-free graphs (ω=2) with arbitrarily high chromatic number.
Correct approach: χ(G) ≥ ω(G) is guaranteed, but χ(G) can be strictly greater. The Petersen graph: ω=2, χ=3.
11. Frequently Asked Questions
Q1. What is the Handshaking Lemma and why does it matter for GATE?
The Handshaking Lemma states ∑deg(v) = 2|E| — the sum of all vertex degrees equals twice the number of edges, because each edge contributes exactly 1 to each of its two endpoints’ degrees. Its practical consequence in GATE problems: (1) You can find a missing degree given the edge count. (2) Every graph has an even number of odd-degree vertices — useful to immediately reject invalid degree sequences. (3) In directed graphs, ∑in-deg = ∑out-deg = |E|, useful for flow/connectivity problems.
Q2. What is the difference between Euler path and Hamiltonian path?
An Euler path traverses every edge exactly once (vertices can repeat); an Euler circuit does this and returns to the start. Condition: connected + exactly 0 (circuit) or 2 (path) vertices of odd degree. Efficient algorithm: Hierholzer’s O(E). A Hamiltonian path visits every vertex exactly once (edges can be skipped); a Hamiltonian circuit does this and returns to start. No efficient algorithm exists — checking Hamiltonicity is NP-complete. For GATE, always check Euler conditions if the problem says “traverse all edges” and treat Hamiltonicity questions as computational complexity problems.
Q3. How many edges does a tree with n vertices have?
A tree with n vertices always has exactly n−1 edges. This follows because: starting from a single vertex (0 edges), to connect n vertices into a single connected component without creating a cycle, you need exactly one edge per additional vertex, giving n−1 total. This is both necessary and sufficient — a connected graph with n vertices and n−1 edges must be a tree (no cycles). A forest (disconnected acyclic graph) with n vertices and k components has n−k edges.
Q4. What is Euler’s formula for planar graphs?
For any connected planar graph: V − E + F = 2 (vertices − edges + faces = 2), where faces include the outer unbounded face. This formula is remarkably robust — it holds for any planar embedding of any connected planar graph. From it we derive: E ≤ 3V−6 (general), E ≤ 2V−4 (bipartite/triangle-free). These bounds are used to prove non-planarity: K₅ has E=10 > 3(5)−6=9 → non-planar; K₃,₃ has E=9 > 2(6)−4=8 (using bipartite bound) → non-planar. The Four Color Theorem (every planar graph has χ ≤ 4) is a deep consequence of planarity.