📘 GRAPH THEORY — COMPLETE EXAM REVISION
NOTES
1. Introduction to Graphs
What is a Graph?
A graph is a collection of dots (called vertices/nodes) connected by lines (called edges).
Formal Definition: A graph G is an ordered pair G = (V, E) where V = set of vertices, E = set of edges.
Basic Graph — Vertices (v1-v4), Edges (e1-e7), Self-Loop & Parallel Edges
📌 Quick Revision: Graph = Vertices + Edges. Written as G = (V, E). Each edge connects two vertices (or a vertex to itself).
2. Types of Edges & Graphs
Self-Loop, Parallel Edges, Simple vs Multi-Graph
• Self-Loop: An edge connecting a vertex to itself. Example: e = (v3, v3)
• Parallel Edges: Two or more edges between the same pair of vertices
• Simple Graph: NO self-loops AND NO parallel edges
• Multi-Graph: Has self-loops or parallel edges (or both)
Page 1 / 18
Self-Loop, Parallel Edges, and Simple vs Multi-Graph
Weighted Graph
A graph where each edge has a numerical value (weight) — can represent distance, cost, time, etc.
Weighted Graph — edges have numerical weights
Other Types
Type Description
Finite Graph Finite number of vertices AND edges
Infinite Graph Infinite vertices or edges
Labeled Graph Edges/vertices have names or values
📌 Quick Revision: Self-loop = vertex to itself. Parallel = multiple edges same pair. Simple = no loops, no parallels.
3. Adjacency & Incidence
Adjacent Vertices: Two vertices directly connected by at least one edge.
Incidence: An edge is incident on its endpoint vertices. A vertex is incident on its connected edges.
Page 2 / 18
Adjacency (vertex-vertex) vs Incidence (vertex-edge)
📌: Adjacent = vertex↔vertex relationship. Incident = vertex↔edge relationship.
4. Degree of a Vertex
The degree of vertex v, written d(v) or deg(v), = number of edges connected to it.
⚠️ A self-loop counts as 2 toward the degree!
Vertex Degrees & Handshaking Lemma Visualization
Type Degree Meaning
Isolated vertex 0 No edges connected
Pendant vertex 1 Exactly one edge
Trivial graph — Graph with only 1 vertex
Page 3 / 18
5. Handshaking Lemma
∑ d(vᵢ) = 2 × E (Sum of ALL vertex degrees = twice the number of edges)
Why? Each edge has 2 endpoints → each edge adds 2 to the total degree count.
Example
Q: Graph with 10 vertices, each of degree 6. How many edges?
A: Sum of degrees = 10 × 6 = 60. By Handshaking: 2E = 60 → E = 30 edges
Important: The number of vertices with odd degree is always EVEN.
📌 Formula: ∑ d(vᵢ) = 2E — Each edge contributes 2 to total degree. Odd-degree vertex count is always even.
6. Matrix Representations
Adjacency Matrix
n × n matrix where A[i][j] = 1 if edge exists between vᵢ and vⱼ, 0 otherwise. Symmetric for undirected graphs.
For multigraphs: A[i][j] = N (number of edges between vᵢ and vⱼ).
Incidence Matrix
n × e matrix where X[i][j] = 1 if edge eⱼ is incident on vertex vᵢ, 0 otherwise.
Graph with Its Adjacency Matrix
Matrix Size Entry Meaning
Adjacency n×n 1 if adjacent, 0 if not
Incidence n×e 1 if edge touches vertex, 0 if not
Page 4 / 18
7. Directed Graphs (Digraphs)
A graph where each edge has a direction (arrow).
Term Symbol Meaning
In-degree deg⁻(v) Edges coming INTO v
Out-degree deg⁺(v) Edges going OUT of v
Source — In-degree = 0 (no incoming edges)
Sink — Out-degree = 0 (no outgoing edges)
Directed Graph with In-degree & Out-degree
Incidence Matrix of Digraph
X[i][j] = +1 if edge eⱼ goes OUT of vᵢ, −1 if INTO vᵢ, 0 if not incident.
8. Special Graphs
Null Graph (Nₙ)
Only vertices, zero edges. All vertices are isolated.
Null Graphs N₃ and N₄
Complete Graph (Kₙ)
Every vertex connected to every other vertex. Degree of each vertex = n − 1.
Page 5 / 18
Edges in Kₙ = n(n−1) / 2
Complete Graphs K₁ through K₅
n Edges
3 3
4 6
5 10
6 15
Regular Graph
All vertices have the same degree r. Called r-regular. Example: Kₙ is (n−1)-regular.
9. Bipartite Graphs
Vertices split into two disjoint sets V₁ and V₂. Every edge connects a V₁ vertex to a V₂ vertex. No edges within same set. No self-
loops.
Page 6 / 18
Bipartite Graph & Complete Bipartite K₂,₃
Key Property: All cycles in a bipartite graph have EVEN length. If a graph has an odd cycle → NOT bipartite.
Complete Bipartite Kₘ,ₙ: Every V₁ vertex connects to every V₂ vertex. Total edges = m × n.
Test: Can you color it with 2 colors? Yes → Bipartite ✓
10. Isomorphism
Two graphs are isomorphic if they have the same structure — you can relabel vertices of one to get the other.
Necessary Conditions (all must be true):
1. Same number of vertices
2. Same number of edges
3. Same degree sequence
Isomorphic Graphs — Same Structure, Different Labels
Warning: These conditions are necessary but NOT sufficient. Must verify edge correspondence too.
Page 7 / 18
11. Subgraphs
G' = (V', E') is a subgraph of G if V' ⊆ V, E' ⊆ E, and all edges in E' connect vertices in V'.
Subgraph Types — Original, Vertex Deletion, Spanning Subgraph
Type What it does
Vertex deletion G−v Remove vertex + ALL its edges
Edge deletion G−e Remove edge, keep all vertices
Induced subgraph G[X] Keep only vertices X and all edges within X
Spanning subgraph Same vertices as G, subset of edges
Cut vertex Its removal disconnects the graph
12. Graph Operations
Operation Vertices Edges
Union G₁ ∪ G₂ V₁ ∪ V₂ E₁ ∪ E₂
Intersection G₁ ∩ G₂ V₁ ∩ V₂ E₁ ∩ E₂
Complement ~G Same as G Edge present ↔ absent flipped
Page 8 / 18
Graph G and Its Complement ~G
13. Walks, Trails, Paths & Cycles
Term Repeated Edges? Repeated Vertices? Open/Closed
Walk ✅ Yes ✅ Yes Either
Trail ❌ No ✅ Yes Either
Path ❌ No ❌ No Open
Tour ❌ No (trail) ✅ Yes Closed
Cycle ❌ No ❌ No (except start=end) Closed
Walk vs Trail vs Path vs Cycle
Length of a walk/trail/path = number of edges (not vertices!).
Distance between two vertices = length of the shortest path.
📌: Walk = anything goes. Trail = no repeated edges. Path = no repeated anything. Cycle = closed path. Tour = closed trail.
14. Connected Graphs
Connected: Path exists between EVERY pair of vertices. Otherwise: disconnected.
Page 9 / 18
Connected Graph (1 component) vs Disconnected (3 components)
Connected component: A maximal connected subgraph. Each isolated vertex = its own component.
Strongly connected (digraph): Directed path exists from x to y AND from y to x for all pairs.
Balanced vertex: in-degree = out-degree.
15. Eulerian Trails & Tours
Seven Bridges of Königsberg (1735)
Euler proved it's impossible to cross each of 7 bridges exactly once → started graph theory!
Seven Bridges of Königsberg — All Vertices Have Odd Degree
Term Definition
Eulerian Trail Uses every edge exactly once (start ≠ end)
Eulerian Tour/Circuit Uses every edge once AND returns to start
Page 10 / 18
⭐ Critical Theorems
Eulerian TOUR exists ⟺ Connected + ALL vertices have EVEN degree
Eulerian TRAIL exists ⟺ Connected + EXACTLY 2 vertices have ODD degree
Eulerian Tour vs Hamiltonian Cycle
Hierholzer's Algorithm (Finding Eulerian Tour)
1. Start at any vertex x, follow unused edges forming a tour back to x
2. If unused edges remain, find vertex w on tour with unused edges
3. Form new tour from w, splice into existing tour at w
4. Repeat until all edges used
Directed Graph Eulerian Conditions
Type Condition
Eulerian Tour (digraph) Balanced (in-deg = out-deg for all) + strongly connected
Eulerian Trail (digraph) outdeg(x)=indeg(x)+1, indeg(y)=outdeg(y)+1, others balanced
16. Hamiltonian Paths & Cycles
Term Definition
Hamiltonian Path Visits every vertex exactly once
Hamiltonian Cycle Visits every vertex once + returns to start
Page 11 / 18
Hamiltonian Path vs Hamiltonian Cycle
Euler vs Hamilton — Key Difference!
Eulerian Hamiltonian
Visits Every EDGE once Every VERTEX once
Efficient algorithm? ✅ Yes (Hierholzer) ❌ No (NP-complete)
⭐ Dirac's Theorem
If n ≥ 3 and EVERY vertex has degree ≥ n/2 → Hamiltonian cycle EXISTS
If some vertex has degree < n/2 → theorem gives NO conclusion (might or might not exist).
Tournaments
A tournament = complete directed graph. Key property: every tournament has a Hamiltonian path!
Tournament — Hamiltonian Path Gives Player Ranking
NP-completeness: No known polynomial-time algorithm to find Hamiltonian cycles in general.
Page 12 / 18
Cycle Length Guarantee
If minimum degree δ(G) ≥ k → G has a cycle of length ≥ k + 1
17. Postman Problem (Chinese Postman)
Find the lowest-cost closed walk using every edge at least once.
Chinese Postman Problem — Pair Odd-Degree Vertices
Steps to Solve:
1. All even degree? → Eulerian tour is the answer!
2. Odd degree vertices? Find all of them (always even count)
3. List all possible pairings of odd-degree vertices
4. For each pairing, find shortest paths and total cost
5. Choose cheapest pairing, duplicate those edges
6. Now all degrees even → find Eulerian tour
Number of pairings for m odd-degree vertices = (m−1)!! = (m−1)(m−3)(m−5)···1
18. Travelling Salesman Problem (TSP)
Find the cheapest Hamiltonian cycle in a complete weighted graph. Visit every city once, return to start, minimize cost.
Page 13 / 18
TSP — Best Cycle A→C→B→D→A costs 27
• Brute force: check all n! orderings → impractical for large n
• Best known algorithm: ≈ n² × 2ⁿ steps
• NP-hard — no known efficient general solution
19. Planar Graphs
A graph is planar if it can be drawn without edges crossing. The drawing divides the plane into faces/regions (including one infinite face).
K₄ Planar (V−E+F=2) vs K₅ Non-Planar (E > 3V−6)
⭐ Euler's Formula (MOST IMPORTANT!)
V − E + F = 2 (for connected planar graphs)
V = vertices, E = edges, F = faces (including infinite face)
Disconnected: F = E − V + (k + 1) where k = number of components
Page 14 / 18
Degree of a Region
= number of edges on its boundary. An edge appearing twice on a boundary contributes 2.
∑ deg(Rᵢ) = 2E (Sum of region degrees = 2 × edges)
⭐ Corollaries
Corollary Formula Condition
1: Edge Bound E ≤ 3V − 6 Simple connected planar, V ≥ 3
Also 3F ≤ 2E, F ≤ 2V − 4 Same
2: Min Degree Has vertex with degree ≤ 5 Connected simple planar
3: No Triangles E ≤ 2V − 4 Planar, no 3-cycles, V ≥ 3
Proving Non-Planarity Examples
K₅: V=5, E=10. Check: 3V−6=9. Is 10≤9? NO → NOT planar!
K₃,₃: V=6, E=9. Bipartite → use E≤2V−4=8. Is 9≤8? NO → NOT planar!
Special Cases for Region Degrees
Condition Formula
All regions have degree exactly k k × F = 2E
All regions have degree ≥ k k × F ≤ 2E
All regions have degree ≤ k k × F ≥ 2E
Elementary Subdivision & Homeomorphism
Subdivision: Replace edge {u,v} with vertex w and edges {u,w} + {w,v}.
Homeomorphic: Two graphs obtainable from each other by subdivisions.
Elementary Subdivision — Adding Vertex w
⭐ Kuratowski's Theorem
G is non-planar ⟺ G contains a subgraph homeomorphic to K₅ or K₃,₃
Practice Problems
Q: Connected planar graph, 25 vertices, 60 edges. Find regions.
A: r = E − V + 2 = 60 − 25 + 2 = 37 regions
Q: Connected planar graph, 20 vertices, each degree 3. Find regions.
A: ∑deg = 20×3=60, so 2E=60, E=30. r = 30−20+2 = 12 regions
Page 15 / 18
20. Graph Coloring
Assign colors to vertices so no two adjacent vertices share a color = proper coloring.
Chromatic Number χ(G) = minimum colors needed for a proper coloring.
Graph Coloring — Chromatic Number χ(G) = 3
Chromatic Numbers of Special Graphs
Graph χ
Null graph Nₙ 1
Bipartite / Tree 2
Even cycle Cₙ 2
Odd cycle Cₙ 3
Complete graph Kₙ n
Complete bipartite Kₘ,ₙ 2
Bounds on Chromatic Number
ω(G) ≤ χ(G) ≤ Δ(G) + 1
(largest clique ≤ chromatic number ≤ max degree + 1)
Clique: A set of vertices all mutually adjacent (forms a complete subgraph inside the graph).
Greedy Coloring Algorithm
1. Order the vertices
2. Color each vertex with the lowest-numbered color not used by any adjacent vertex
3. Continue until all colored
⚠️ Greedy doesn't always give the optimal result — depends on vertex ordering!
Page 16 / 18
⭐ Four Color Theorem
Every planar graph can be properly colored with at most 4 colors.
Proved in 1977 by Appel & Haken (first major computer-based proof)
Applications
Application Vertices Edges Colors
Map coloring Regions Shared borders Colors
Exam scheduling Courses Shared students Time slots
Frequency assignment Towers Signal overlap Frequencies
Room assignment Events Time overlap Rooms
Sudoku 81 cells Same row/col/box Digits 1-9
🔥 CHEAT SHEET — All Formulas & Key Points
All Formulas
# Formula When to Use
1 ∑ d(vᵢ) = 2E Handshaking Lemma
2 Edges in Kₙ = n(n−1)/2 Complete graph
3 Edges in Kₘ,ₙ = m×n Complete bipartite
4 V−E+F=2 Euler's formula (connected planar)
5 F = E − V + (k+1) Disconnected planar (k components)
6 E ≤ 3V − 6 Simple connected planar, V≥3
7 E ≤ 2V − 4 Triangle-free planar, V≥3
8 ∑ deg(Rᵢ) = 2E Sum of region degrees
9 3F ≤ 2E Simple planar face bound
10 ω(G) ≤ χ(G) ≤ Δ(G)+1 Chromatic number bounds
Key Theorems
Theorem Statement
Handshaking ∑ degrees = 2 × edges
Euler's Formula V−E+F=2
Four Color Any planar graph: χ ≤ 4
Kuratowski Non-planar ⟺ has subgraph ≅ K₅ or K₃,₃
Dirac n≥3, all deg ≥ n/2 → Hamiltonian cycle
Eulerian Tour Connected + all even degree
Eulerian Trail Connected + exactly 2 odd-degree vertices
Page 17 / 18
Quick Definitions
Term Meaning
Walk Any sequence, can repeat edges/vertices
Trail No repeated edges
Path No repeated edges or vertices
Cycle Closed path (start=end)
Tour Closed trail
Hamiltonian Uses every VERTEX once
Eulerian Uses every EDGE once
Source/Sink In-deg=0 / Out-deg=0 in digraph
Clique Complete subgraph
Cut vertex Removal disconnects graph
Problem-Solving Tips
Task Method
Find edges from degrees ∑deg = 2E
Find faces V−E+F=2
Check planarity E ≤ 3V−6 (or 2V−4 if bipartite)
Check Eulerian Count odd-degree vertices (0→tour, 2→trail)
Check Hamiltonian Dirac: all deg ≥ n/2?
Chromatic number Clique size (lower) to Δ+1 (upper)
GOOD LUCK ON YOUR EXAM! YOU GOT THIS! 🎯
Page 18 / 18