Graph Theory
A graph is dots joined by lines. That is the whole concept — the entire unit is vocabulary for the dots, the lines, and a handful of procedures for finding routes through them. Real applications: road networks, social networks, circuit boards, internet routing.
Vertices (V) = the dots. Edges (E) = the lines.
A graph is written G = (V, E). Learn the words vertex / node and edge / link / arc — exams mix them up on purpose.
1. Anatomy of a Graph and Terminology
| Term | Meaning |
|---|---|
| Vertex / node | A single point in the graph |
| Edge / link | A line joining two vertices |
| Adjacent | Two vertices are adjacent if an edge joins them |
| Degree, deg(v) | Number of edges touching v. A loop counts twice |
| Loop | An edge from a vertex back to itself |
| Parallel edges | Two or more edges joining the same pair of vertices |
| Path | A sequence of vertices where each consecutive pair is joined by an edge |
| Cycle | A path that starts and ends at the same vertex, with no other repetition |
| Walk | A path where vertices may repeat |
| Length | Number of edges in the path (not vertices) |
| Simple graph | No loops and no parallel edges |
| Complete graph Kₙ | Every pair of vertices is joined — each vertex has degree n−1 |
| Subgraph | A graph made from some vertices and some edges of the original |
| Order |V| | How many vertices |
| Size |E| | How many edges |
A path from A to C via B, written A–B–C, has length 2 (two edges: A–B and B–C), even though it visits three vertices. Students lose marks on this every single year. Count the lines, not the dots.
Connected vs disconnected
- Connected — you can get from any vertex to any other by following edges
- Disconnected — some vertices are stranded in a separate piece
- Component — a maximal connected piece of a disconnected graph
Complete graph Kₙ in one line
Every vertex is joined to every other, so:
|E| = n(n−1)/2
K₃ is a triangle, K₄ is a triangle with a dot in the middle, K₅ is the pentagon-and-star.
2. Directed and Undirected Graphs
Undirected
Edges are two-way. A road you can drive both ways. Drawn with a plain line.
{A, B} = {B, A}
Used for: friendships, mutual connections, physical cables.
Directed (digraph)
Edges are one-way. Drawn with an arrowhead.
(A, B) ≠ (B, A)
Used for: web links, "follows", one-way streets, task dependencies.
Split it in two:
- Out-degree d⁺(v) = arrows leaving v (how many things v points to)
- In-degree d⁻(v) = arrows entering v (how many things point to v)
For every vertex: in-degree = out-degree, summed over the whole graph. This is the directed version of the handshaking lemma.
3. Degree of a Vertex & the Handshaking Lemma
Question: A graph has 6 vertices with degrees 3, 2, 4, 3, 1, 2. How many edges?
|E| = 15/2 = 7.5
7.5 is not a whole number — so the graph as stated is impossible. That is the point of the trick: the sum of degrees must be even.
Before anything else in a graph question, add up the degrees.
- Total is even → plausible, carry on. Then |E| = sum/2.
- Total is odd → impossible. Say so. This is a free mark and it takes 10 seconds.
Also useful: every undirected graph with n vertices needs at least n − 1 edges to be connected. If a "connected" graph has fewer than n − 1 edges, it is not connected.
• A graph with n vertices has at most n(n−1)/2 edges (that is Kₙ)
• A regular graph has all vertices of the same degree; d must be even if n is odd
4. Adjacency Matrix
An adjacency matrix stores the graph as a table of 0s and 1s: rows are vertices as source, columns are vertices as target.
| Property | What it looks like | Why |
|---|---|---|
| Undirected graph | Matrix is symmetric (aᵢⱼ = aⱼᵢ) | If u joins v, then v joins u |
| No loops | Diagonal entries are 0 | A loop would need aᵢᵢ = 1 |
| Degree of vᵢ | Sum of row i (undirected) | Row i lists everything vᵢ touches |
| Directed graph | Not necessarily symmetric | aᵢⱼ = 1 does not force aⱼᵢ = 1 |
| Out-degree | Sum of row i (directed) | Row = leaving vᵢ |
| In-degree | Sum of column i (directed) | Column = arriving at vᵢ |
A loop makes the matrix not symmetric unless you put a 2 in the diagonal cell. That is the standard convention: aᵢᵢ = 2 for a loop, because a loop contributes 2 to the degree.
5. Incidence Matrix
The incidence matrix is different: it relates vertices to edges, not vertices to vertices. The columns are the edges.
| Adjacency matrix | Incidence matrix | |
|---|---|---|
| Size | n × n (vertices × vertices) | n × m (vertices × edges) |
| Entries mean | "is vᵢ joined to vⱼ?" | "is vᵢ an end of eⱼ?" |
| Row sum = degree? | Yes (undirected) | Yes |
| Column sum | degree (undirected) / in-degree (directed) | always 2 in an undirected graph |
| Symmetric? | Yes if undirected | No |
Students mix these up. Fix it with a memory line:
- Adjacent = vertex ↔ vertex. Both are dots. "Two dots are neighbours."
- Incident = vertex ↔ edge. A dot touches a line. "The dot is on the line."
- Adjacency matrix = vertex ↔ vertex. Incidence matrix = vertex ↔ edge.
Mnemonic: "A for Adjacent (A for All-points), I for Incidence (I touches the line in between points)."
Graph on {a, b, c} with edges: ab, bc.
Adjacency (a is row 1):
| 1 0 1 |
| 0 1 0 |
Check: row 1 sums to 1 → deg(a) = 1 ✓. Symmetric ✓. Total edges = (1+2+1)/2 = 2 ✓.
Incidence (columns = ab, bc):
| 1 1 |
| 0 1 |
Check: each column sums to 2 ✓. Row sums 1, 2, 1 = the degrees ✓.
6. Dijkstra's Shortest Path Algorithm
Dijkstra finds the cheapest route from one starting vertex to every other vertex, when every edge has a non-negative weight (cost, distance, time).
Setup. Start at S. Write ∞ for everything you cannot reach yet.
Step 1 — from S. Smallest unvisited is S (dist 0). Relax its two edges:
visited: {S} permanent labels: S=0, A=4, B=4
Step 2 — pick the smallest. A and B both have 4; take A.
Labels: S=0, A=4, B=4, C=12, D=∞, E=∞, F=∞ visited: {S, A}
Step 3 — smallest unvisited is B (4).
Labels: S=0, A=4, B=4, C=10, D=∞, E=6, F=∞ visited: {S, A, B}
Step 4 — smallest unvisited is E (6).
Labels: S=0, A=4, B=4, C=10, D=∞, E=6, F=11 visited: {S, A, B, E}
Step 5 — smallest unvisited is C (10).
Labels: S=0, A=4, B=4, C=10, D=19, E=6, F=11 visited: {S, A, B, E, C}
Step 6 — smallest unvisited is F (11).
Final: S=0, A=4, B=4, C=10, D=18, E=6, F=11
Shortest path to D: S → B → E → F → D = 4 + 2 + 5 + 7 = 18
The most reliable way to run Dijkstra on paper is a table with two columns per vertex: permanent (final, written in ink) and tentative (best guess so far, in pencil).
- Pick the smallest tentative → move it to permanent.
- Permanent labels never change again. That is what makes Dijkstra correct.
- Tentative = min(itself, current + edge weight).
- Never "un-permanent" a vertex. If your table says otherwise, you have made an error.
Dijkstra needs non-negative weights. With a negative edge it can give the wrong answer, and you need Bellman–Ford instead. In practice: distances, costs and times are always positive, so Dijkstra is safe.
Dijkstra finds the cheapest path in a weighted graph — think money or kilometres.
BFS (breadth-first search) finds the path with the fewest edges in an unweighted graph — think "fewest hops" in an unweighted friend network.
They give the same answer when all edges have equal weight. If the question gives no numbers on the edges, you want BFS.
7. Graph Colouring
Colour the vertices so that no two adjacent vertices share a colour. The point is that fewer colours means fewer resources — fewer channels, fewer time slots, fewer frequency bands.
Standard results worth memorising
| Graph | Chromatic number | Reason |
|---|---|---|
| Empty graph (no edges) | 1 | Everything can be one colour |
| Tree / forest | 2 | Bipartite — alternate two colours |
| Cycle Cₙ, n even | 2 | Alternate around, closes cleanly |
| Cycle Cₙ, n odd | 3 | Alternating fails at the last vertex |
| Bipartite graph | 2 | No odd cycles present |
| Complete graph Kₙ | n | Every vertex touches every other |
| Any planar graph | ≤ 4 | Four-colour theorem |
Try to 2-colour a 5-cycle v₁–v₂–v₃–v₄–v₅–v₁:
but v₅ is adjacent to v₁, and both are RED. ✗ CONFLICT
So 2 colours fail. Try 3:
- Try to divide the vertices into two groups X and Y so that every edge goes from X to Y. (Think chessboard colours, or "boys and girls".)
- Succeeded? The graph is bipartite and χ = 2. Two colours always work, and 2 is the minimum unless there are no edges at all.
- Failed? There is an odd cycle inside, so χ ≥ 3.
Super-fast odd-cycle hunt: if you can trace a closed loop with an odd number of edges (3, 5, 7…), the graph is not bipartite. This catches most exam questions in seconds.
Self-check
Open to see the answers
1. A graph has degrees 2, 3, 3, 4. How many edges? Is it possible?
Valid, since the sum is even. Also note: 2 odd-degree vertices (the two 3s) — an even number, as required.
2. Can a simple graph have vertices of degree 1, 1, 1? What about 1, 1, 1, 1?
degrees 1,1,1,1: sum = 4, |E| = 2 → possible: two separate edges (two disjoint pairs).
3. Build the adjacency matrix for V = {1,2,3,4}, E = {(1,2), (2,3), (3,4), (4,1)}.
2 adjacent to 1 and 3 → 1 0 1 0
3 adjacent to 2 and 4 → 0 1 0 1
4 adjacent to 1 and 3 → 1 0 1 0
Matrix is symmetric ✓ (undirected). Row sums all = 2 → every vertex has degree 2 ✓. Total edges = 8/2 = 4 ✓. This is the 4-cycle C₄, so χ = 2.
4. Why does Dijkstra give the wrong answer if edge weights can be negative?