🧬 Bioinformatics Protein interaction networks, genome assembly.
🗄 Databases Entity-relationship diagrams are graphs. Graph databases (Neo4j) store data as graphs.
Key idea: Whenever you have objects and relationships between them, a graph is a natural model.
9.1.2
9.1.2 — What is a Graph?
Definition (Simple Graph).
A simple graph \(G = (V, E)\) consists of a non-empty set \(V\) of vertices (nodes) and a set \(E\) of edges, where each edge is an unordered pair \(\{u, v\}\) of distinct vertices.
If \(\{u,v\} \in E\), then \(u\) and \(v\) are adjacent
The edge \(\{u,v\}\) is incident to both \(u\) and \(v\)
The degree \(\deg(v)\) = number of edges incident to \(v\)
Figure 9.1: The graph on \(V=\{A,B,C,D\}\)
Each vertex has degree 2 here.
9.1.3
9.1.3 — The Handshaking Lemma
Theorem (Handshaking Lemma).
For any graph \(G = (V, E)\):
$$\sum_{v \in V} \deg(v) = 2|E|$$
Why?
Every edge \(\{u,v\}\) contributes exactly 2 to the degree sum — once for \(u\) and once for \(v\). Like a handshake: two hands involved per shake.
Corollary: In any graph, the number of vertices with odd degree is even.
Example
Graph with 5 edges:
Degree sum = 10.
Possible degrees: 3, 3, 2, 2 ✓
Not possible: 3, 3, 3, 1 ✗ (sum = 10 ✓, but check odd count — three odd degrees is impossible!)
CS Application: In a network, if we count all connections per router, we get twice the number of cables. Useful for sanity-checking network data!
9.1.4
9.1.4 — Storing Graphs in a Computer
Two main representations for a graph \(G=(V,E)\) with \(n\) vertices:
Adjacency Matrix
An \(n \times n\) matrix \(A\) where \(A_{ij} = 1\) if \(\{i,j\} \in E\), else 0.
A
B
C
D
A
0
1
0
1
B
1
0
1
0
C
0
1
0
1
D
1
0
1
0
Space: \(O(n^2)\). Check edge: \(O(1)\).
Adjacency List
For each vertex, store the list of its neighbours.
A: [B, D]
B: [A, C]
C: [B, D]
D: [A, C]
Space: \(O(n + |E|)\). Better for sparse graphs.
When to use which? Dense graph → matrix. Sparse graph → list.
9.1.5
9.1.5 — Graph Isomorphism
Definition. Two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) are isomorphic if there is a bijection \(f: V_1 \to V_2\) such that \(\{u,v\} \in E_1 \iff \{f(u), f(v)\} \in E_2\).
We write \(G_1 \cong G_2\).
Isomorphic graphs are structurally identical — just with different vertex labels.
Graph Invariants — properties preserved by isomorphism:
Number of vertices \(|V|\)
Number of edges \(|E|\)
Degree sequence (sorted list of degrees)
Number of connected components
Presence of cycles of a given length
If any invariant differs, the graphs are not isomorphic. If all match, they might be isomorphic — you still need to find \(f\).
G₁ has a cycle (triangle); G₂ does not — they differ in structure.
9.1.6
9.1.6 — Special Types of Simple Graph
Complete graph \(K_n\)
Every pair of vertices is connected. Has \(\binom{n}{2} = \frac{n(n-1)}{2}\) edges.
Cycle graph \(C_n\)
Vertices arranged in a cycle. Every vertex has degree 2. Has \(n\) edges.
Bipartite graph \(K_{m,n}\)
Vertices split into two sets; edges only go between sets. Has \(mn\) edges.
Also know: Path graph \(P_n\) (a straight chain), Empty graph (no edges), Regular graph (all degrees equal).
9.1.Q
Knowledge Check — Section 9.1
Q1. A simple graph has 6 vertices each of degree 3. How many edges does it have?
By the Handshaking Lemma: \(\sum \deg(v) = 6 \times 3 = 18 = 2|E|\), so \(|E| = 9\).
Q2. Two graphs both have 5 vertices and 6 edges. Can we immediately conclude they are isomorphic?
Invariants like \(|V|\) and \(|E|\) must match, but they are not sufficient. Two graphs can share all invariants yet be non-isomorphic if their structural connections differ.
9.2
9.2 — Graphs and their Properties
Paths, connectivity, Euler circuits, Hamilton paths, and planarity
9.2.1
9.2.1 — Paths, Walks, and Circuits
Walk: A sequence of vertices \(v_0, v_1, \ldots, v_k\) where each consecutive pair \(\{v_i, v_{i+1}\} \in E\). Edges and vertices may repeat.
Path: A walk with no repeated vertices.
Circuit (Closed Walk): A walk that starts and ends at the same vertex.
Cycle: A circuit with no repeated vertices (except start = end).
Example — the graph below
Walk: \(A \to B \to C \to B\) (repeats B)
Path: \(A \to B \to C \to D\) (no repeats)
Cycle: \(A \to B \to C \to D \to A\)
9.2.2
9.2.2 — Connected Graphs and Trees
Connected Graph: A graph where there is a path between every pair of vertices.
Tree: A connected graph with no cycles.
Forest: A graph with no cycles (possibly disconnected); each component is a tree.
A tree on \(n\) vertices has exactly \(n-1\) edges. This is a useful result we will use in Section 9.3.
9.2.3
9.2.3 — The Bridges of Königsberg
In 1736, Leonhard Euler asked: "Can you walk through the city of Königsberg crossing each of its 7 bridges exactly once?"
We model this as a graph:
Land masses = vertices
Bridges = edges
Euler Path: A walk that visits every edge exactly once.
Euler Circuit: An Euler path that starts and ends at the same vertex.
This is different from a Hamiltonian path, which visits every vertex exactly once.
Königsberg graph: degrees are 3, 3, 3, 5 — all odd!
9.2.4
9.2.4 — Euler's Theorem
Theorem (Euler, 1736).
A connected graph \(G\) has an Euler circuit if and only if every vertex has even degree.
A connected graph \(G\) has an Euler path (but not circuit) if and only if it has exactly two vertices of odd degree (those are the start and end).
Königsberg — revisited
Degrees: 3, 3, 3, 5 → all odd (4 odd-degree vertices).
Since there are more than 2 odd-degree vertices, no Euler path exists.
This solved a 300-year puzzle in a single elegant theorem — and founded the field of graph theory!
Sketch of proof idea
Every time you enter a vertex via one edge, you must leave via another → pairs of edges consumed → even degree needed.
Start/end vertices break this pairing → exactly 2 odd-degree vertices allowed for an open Euler path.
9.2.5
9.2.5 — Hamiltonian Paths
Hamiltonian Path: A path that visits every vertex exactly once. Hamiltonian Circuit: A Hamiltonian path that starts and ends at the same vertex.
The hard problem: Unlike Euler circuits, there is no simple "if and only if" condition for Hamiltonian circuits.
Finding a Hamiltonian circuit is an NP-complete problem — no efficient algorithm is known for the general case.
CS connection — Travelling Salesman Problem (TSP): Find the shortest Hamiltonian circuit in a weighted graph. Used in logistics, chip design, DNA sequencing. Still an active research area!
Dirac's Theorem (sufficient, not necessary):
If \(G\) is a simple graph on \(n \geq 3\) vertices and every vertex has degree \(\geq n/2\), then \(G\) has a Hamiltonian circuit.
Euler vs Hamilton:
Euler → traverse every edge → simple degree condition ✓
Hamilton → visit every vertex → hard, no simple condition ✗
9.2.6
9.2.6 — Planar Graphs and Euler's Formula
Planar Graph: A graph that can be drawn in the plane so that no two edges cross.
Euler's Formula (for planar graphs):
For a connected planar graph drawn in the plane:
$$V - E + F = 2$$
where \(V\) = vertices, \(E\) = edges, \(F\) = faces (including the outer infinite face).
Example: The Cube graph
\(V = 8,\ E = 12,\ F = 6\)
Check: \(8 - 12 + 6 = 2\) ✓
Application: \(K_5\) and \(K_{3,3}\) are non-planar (Kuratowski's theorem). This matters for printed circuit board design!
9.2.Q
Knowledge Check — Section 9.2
Q1. A connected graph has exactly 2 vertices of odd degree. What can we say?
By Euler's theorem, exactly 2 odd-degree vertices means an Euler path exists from one odd-degree vertex to the other, but no Euler circuit (which requires all even degrees).
Q2. A connected planar graph has \(V = 10\) vertices and \(E = 15\) edges. How many faces does it have?
By Euler's formula: \(F = 2 - V + E = 2 - 10 + 15 = 7\).
9.3
9.3 — Extra Topics in Graph Theory
Dijkstra's shortest path algorithm and tree structures
9.3.1
9.3.1 — Weighted Graphs and Shortest Paths
Weighted Graph: A graph where each edge \(\{u,v\}\) has an associated weight (cost, distance, time) \(w(u,v) \in \mathbb{R}^+\).
Shortest path problem: Given a weighted graph and a source vertex \(s\), find the minimum-weight path from \(s\) to every other vertex.
Applications:
GPS navigation (road distances)
Network routing (latency)
Airline scheduling (cost)
Game AI (movement cost)
Shortest path A→D? Is it A→B→D (cost 9) or A→C→D (cost 5)?
9.3.2
9.3.2 — Dijkstra's Algorithm
Finds shortest paths from source \(s\) to all other vertices. Requires non-negative weights.
1 Assign distance 0 to source \(s\), \(\infty\) to all others.
2 Mark all vertices as unvisited. Set source as current.
3 For current vertex \(u\): for each unvisited neighbour \(v\), compute tentative distance \(d(u) + w(u,v)\). If this is less than \(d(v)\), update \(d(v)\).
4 Mark \(u\) as visited.
5 Set current = unvisited vertex with smallest distance. Repeat from Step 3 until all visited.
Time complexity: \(O((V + E)\log V)\) with a priority queue.
Trace on the graph (source = A)
Step
Visited
d(A)
d(B)
d(C)
d(D)
Init
—
0
∞
∞
∞
Visit A
{A}
0
4
2
∞
Visit C
{A,C}
0
4
2
5
Visit B
{A,C,B}
0
4
2
5
Visit D
{A,C,B,D}
0
4
2
5
Shortest path A→D = 5, via A→C→D.
9.3.3
9.3.3 — Trees and their Applications
Rooted Tree: A tree with one vertex designated as the root. This defines parent/child relationships.
Spanning Tree: A subgraph of a connected graph \(G\) that is a tree containing all vertices of \(G\).
Why trees matter in CS:
Binary search trees → \(O(\log n)\) search
Syntax/parse trees → compilers & interpreters
Decision trees → machine learning models
Minimum spanning trees → network design (minimise cable cost)
File systems → hierarchical directory structure
9.3.Q
Knowledge Check — Section 9.3
Q1. Dijkstra's algorithm is guaranteed to work correctly when:
Dijkstra's greedy approach assumes that once a vertex is visited, its shortest distance is finalised. A negative edge could later provide a shorter path, invalidating this assumption. Use Bellman-Ford for negative weights.
Q2. A spanning tree of a connected graph \(G\) with 8 vertices has how many edges?
Any tree on \(n\) vertices has exactly \(n-1\) edges. A spanning tree includes all 8 vertices, so it has 7 edges, regardless of the original graph.
End
Week 9 Summary
9.1 — Basics
Graph \(G = (V,E)\)
Handshaking Lemma
Adjacency matrix & list
Isomorphism & invariants
Special graphs: \(K_n\), \(C_n\), \(K_{m,n}\)
9.2 — Properties
Paths, cycles, connectivity
Trees: connected + acyclic
Euler: even degrees ↔ circuit
Hamilton: NP-hard in general
Euler's formula: \(V-E+F=2\)
9.3 — Algorithms
Weighted graphs
Dijkstra's algorithm
Spanning trees
Tree applications in CS
Big picture: Graph theory gives us the language and tools to reason about connections — whether between cities, computers, proteins, or people.
Assessment reminder: Problem Sheet questions will test your ability to apply these definitions, find Euler circuits, apply Dijkstra's, and use Euler's formula. Practice with the tutorial exercises!