Graph Theory
Graphs and their terminology, the famous families $K_n, C_n, W_n, Q_n, K_{m,n}$, bipartite graphs, and Euler & Hamiltonian paths.
6.1 Graph Terminology
Vocabulary you must know
- Adjacent vertices: $u, v$ adjacent iff $\{u, v\} \in E$.
- Incident: edge $e = \{u,v\}$ is incident with $u$ and with $v$.
- Loop: edge from $v$ to itself.
- Multi-edge: two edges with the same endpoints.
- Degree $\deg(v)$: number of edges incident to $v$. Loops contribute 2.
- Isolated vertex: degree 0.
- Pendant vertex: degree 1.
- Neighborhood $N(v)$: set of vertices adjacent to $v$.
- Path: sequence of vertices $v_0, v_1, \ldots, v_k$ with each consecutive pair an edge.
- Cycle: a path that returns to its start with no repeated vertices except endpoints.
- Connected: there's a path between every pair.
- Connected component: maximal connected subgraph.
- Cut vertex / bridge: removal disconnects the graph.
6.2 Types of graphs
| Type | Directed? | Multi-edges? | Loops? |
|---|---|---|---|
| Simple graph | No | No | No |
| Multigraph | No | Yes | No |
| Pseudograph | No | Yes | Yes |
| Simple directed graph | Yes | No | No |
| Directed multigraph | Yes | Yes | Yes |
Handshaking Lemma
Why: each edge contributes 2 to the degree sum (one for each endpoint). For directed graphs, $\sum \deg^+(v) = \sum \deg^-(v) = |E|$.
Corollary: even number of odd-degree vertices
Since the sum is even, and even-degree contributions add to even, the odd-degree contributions must also sum to even — which only happens if there's an even count of them.
Bounds from degree
Let $G$ have $v$ vertices, $e$ edges, max degree $M$ and min degree $m$: $$\dfrac{2e}{v} \geq m, \quad \dfrac{2e}{v} \leq M.$$ The left side is the average degree; it lies between $m$ and $M$. Proof by the handshake lemma.
6.4 Some Common Graphs
$K_n$ — complete graph on $n$ vertices
Every pair of distinct vertices is connected. Every vertex has degree $n-1$, so by handshake $|E| = n(n-1)/2$.
(Example: $K_4$, 4 vertices, 6 edges, each degree 3.)
$C_n$ — cycle graph on $n$ vertices
Vertices in a single closed loop: $v_1 - v_2 - \cdots - v_n - v_1$. Every vertex has degree 2; $|E| = n$.
$C_5$: 5 vertices, 5 edges.
$W_n$ — wheel graph
$C_n$ plus a "hub" vertex connected to all $n$ cycle vertices. Hub has degree $n$; rim vertices have degree 3. Total vertices: $n+1$. Total edges: $n + n = 2n$.
$W_5$: cycle $C_5$ + hub. 6 vertices, 10 edges.
$Q_n$ — $n$-cube (hypercube)
Vertices: all $n$-bit binary strings ($2^n$ of them). Two vertices adjacent iff they differ in exactly one bit. Each vertex has degree $n$; total edges $= n\cdot 2^{n-1}$.
$Q_3$: 8 vertices, each degree 3, $|E| = 12$.
$K_{m,n}$ — complete bipartite graph
Two parts of sizes $m, n$; every left vertex connected to every right vertex. $|E| = mn$. Degrees: left vertices have degree $n$, right have degree $m$.
$K_{2,2}$: 4 vertices, 4 edges.
Summary table
| Graph | $|V|$ | $|E|$ | Each degree |
|---|---|---|---|
| $K_n$ | $n$ | $\binom{n}{2} = n(n-1)/2$ | $n-1$ |
| $C_n$ | $n$ | $n$ | $2$ |
| $W_n$ | $n+1$ | $2n$ | hub: $n$, rim: $3$ |
| $Q_n$ | $2^n$ | $n\cdot 2^{n-1}$ | $n$ |
| $K_{m,n}$ | $m+n$ | $mn$ | left $n$, right $m$ |
6.5 Bipartite Graphs
Characterization theorem
Algorithmic check: BFS from any vertex, alternating colours. If you hit a conflict, the graph contains an odd cycle.
Which standard graphs are bipartite?
- $K_n$: bipartite iff $n \leq 2$. (For $n \geq 3$ it contains a triangle, an odd cycle.)
- $C_n$: bipartite iff $n$ is even.
- $W_n$: never bipartite (the hub + two adjacent rim vertices form a triangle).
- $Q_n$: always bipartite. Partition by parity of bit count.
- $K_{m,n}$: always bipartite (by construction).
Edge bound for bipartite simple graphs
Claim. If $G$ is a bipartite simple graph with $v$ vertices and $e$ edges, then $e \leq v^2/4$.
Proof. Let $|V_1| = a, |V_2| = b = v - a$. The maximum number of edges (achieved by $K_{a,b}$) is $ab$. By AM–GM, $ab \leq ((a+b)/2)^2 = v^2/4$. ∎
Hall's Marriage Theorem (perfect matchings)
6.6a Euler Paths & Circuits
Euler circuit: an Euler path that starts and ends at the same vertex.
Existence (Euler's theorem)
• an Euler circuit $\iff$ every vertex has even degree;
• an Euler path (non-circuit) $\iff$ exactly two vertices have odd degree (and you must start at one and end at the other).
The Seven Bridges of Königsberg
Modeling the four landmasses as vertices and the seven bridges as edges, you get a multigraph with degrees $(3, 3, 3, 5)$ — all odd. Four odd-degree vertices means no Euler path exists. Hence the citizens couldn't do it.
Example. Does $K_5$ have an Euler circuit?
$K_5$: every vertex has degree 4 (even). So yes — an Euler circuit exists. (You can verify by drawing the star pentagram.)
Example. Does $K_4$ have an Euler circuit?
$K_4$: every vertex has degree 3 (odd). Four odd-degree vertices → no Euler path or circuit.
For directed graphs
An Euler circuit exists $\iff$ graph is connected (in the underlying undirected sense) and $\deg^+(v) = \deg^-(v)$ for every vertex.
6.6b Hamiltonian Paths & Cycles
Hamiltonian cycle: a Hamiltonian path that returns to the start.
No simple characterization!
Unlike Euler paths, there's no easy degree-based test. Deciding Hamiltonicity is NP-complete.
Sufficient (but not necessary) conditions
Ore (1960). If $\deg(u) + \deg(v) \geq n$ for every nonadjacent pair $u, v$, then $G$ has a Hamiltonian cycle. (Generalises Dirac.)
Which standard graphs are Hamiltonian?
- $K_n$ ($n \geq 3$): always Hamiltonian.
- $C_n$: trivially Hamiltonian (the cycle itself).
- $W_n$: Hamiltonian (go around the rim).
- $Q_n$ ($n \geq 1$): Hamiltonian. Construction via Gray code.
- $K_{m,n}$ with $m = n$: Hamiltonian. With $m \neq n$: not Hamiltonian (any cycle in a bipartite graph has even length and must alternate sides; needs $m = n$).
Euler vs. Hamilton at a glance
| Visits each… | Easy test? | |
|---|---|---|
| Euler path/circuit | edge once | YES — count odd-degree vertices |
| Hamilton path/cycle | vertex once | NO — NP-complete in general |
Interactive Graph Sandbox
Click in the empty canvas space to create vertices. Hold Shift and drag from one vertex to another to draw edges. Hover and press Backspace or Delete to delete vertices/edges.
Graph Properties
Problem Bank — Graph Theory
How many vertices and edges in: (a) $K_n$, (b) $C_n$, (c) $W_n$, (d) $K_{m,n}$, (e) $Q_n$.
Show solution
- (a) $K_n$: $n$ vertices, $\binom{n}{2} = n(n-1)/2$ edges.
- (b) $C_n$: $n$ vertices, $n$ edges.
- (c) $W_n$: $n+1$ vertices, $2n$ edges.
- (d) $K_{m,n}$: $m + n$ vertices, $mn$ edges.
- (e) $Q_n$: $2^n$ vertices, $n\cdot 2^{n-1}$ edges.
For what $n$ are these bipartite: (a) $K_n$, (b) $C_n$, (c) $W_n$, (d) $Q_n$?
Show solution
- (a) $K_n$ bipartite iff $n \leq 2$.
- (b) $C_n$ bipartite iff $n$ is even.
- (c) $W_n$ never bipartite (always has a triangle through hub).
- (d) $Q_n$ always bipartite — partition by bit-count parity.
Find the degree sequence of: (a) $K_4$, (b) $C_4$, (c) $W_4$, (d) $K_{2,3}$, (e) $Q_3$, (f) $K_{m,n}$, (g) $K_n$.
Show solution
- (a) $K_4$: $(3,3,3,3)$.
- (b) $C_4$: $(2,2,2,2)$.
- (c) $W_4$: $(4,3,3,3,3)$ — hub plus four rim.
- (d) $K_{2,3}$: each of the 2 left vertices has degree 3; each of the 3 right has degree 2: $(3,3,2,2,2)$.
- (e) $Q_3$: every vertex has degree 3: $(3,3,3,3,3,3,3,3)$.
- (f) $K_{m,n}$: $m$ vertices of degree $n$, $n$ of degree $m$.
- (g) $K_n$: all degree $n-1$, repeated $n$ times.
For each degree sequence, how many edges? Draw a graph with that sequence:
(a) $4, 3, 3, 2, 2$ (b) $5, 2, 2, 2, 2, 1$.
Show solution
(a) Sum = 14 → $|E| = 7$. Example: 5 vertices labeled $a,b,c,d,e$; $a$ adjacent to all others (degree 4), $b$ adjacent to $a, c, d$ (degree 3), $c$ adjacent to $a, b, e$ (degree 3), $d$ adjacent to $a, b$ (degree 2), $e$ adjacent to $a, c$ (degree 2). Verify: $a$ has $\{b,c,d,e\}$ ⟹ 4 ✓; etc.
(b) Sum = 14 → $|E| = 7$. The degree-5 vertex is adjacent to all 5 others. The remaining 5 vertices form a subgraph; their degree-sum (after subtracting 1 per edge to centre) is $1+1+1+1+0=4$ — so 2 edges among the rim. Construction: hub $h$ connects to all 5 (call them $a,b,c,d,e$), plus the rim has 2 disjoint edges, e.g. $a\text{–}b, c\text{–}d$. Then $a, b, c, d$ have degree 2, and $e$ has degree 1. ✓
Show $\dfrac{2e}{v} \geq m$ and $\dfrac{2e}{v} \leq M$, where $M, m$ are max and min degrees.
Show solution
By handshake, $\sum_v \deg(v) = 2e$. Then $v\cdot m \leq \sum \deg(v) \leq v\cdot M$, giving $m \leq 2e/v \leq M$. ∎
For which $n$ are $K_n, C_n, W_n, Q_n$ regular? When is $K_{m,n}$ regular? Find $|V|$ of a 4-regular graph with 10 edges.
Show solution
- $K_n$ is $(n-1)$-regular for every $n$.
- $C_n$ is 2-regular for every $n \geq 3$.
- $W_n$ is regular only if hub degree $n$ equals rim degree 3, i.e., $n = 3$ — then $W_3 = K_4$ is 3-regular.
- $Q_n$ is $n$-regular for every $n$.
- $K_{m,n}$ is regular iff $m = n$.
4-regular with $e = 10$: $\sum\deg(v) = 4v = 2e = 20$, so $v = 5$. (For example, $K_5$.)
Show that for a bipartite simple graph with $v$ vertices and $e$ edges, $e \leq v^2/4$.
Show solution
Let parts have sizes $a$ and $v - a$. Max edges $= a(v-a)$. Maximize over $a$: take derivative or note that $a(v-a) \leq (v/2)^2$ by AM-GM. So $e \leq v^2/4$. ∎
Prove: every undirected graph has an even number of vertices of odd degree.
Show solution
Split: $\sum_v \deg(v) = \sum_{\text{even-deg}} \deg(v) + \sum_{\text{odd-deg}} \deg(v) = 2|E|$ (even).
The first sum (sum of evens) is even. So the second sum (sum of odds) must also be even. A sum of odd numbers is even iff there are an even count of them. ∎
Show that $G$ is bipartite iff it has no odd-length cycle.
Show solution
$(\Rightarrow)$ If bipartite, any cycle alternates sides $V_1, V_2, V_1, \ldots$ — must return to its starting side, so cycle length is even.
$(\Leftarrow)$ Assume no odd cycle. We construct a 2-colouring. For each connected component, pick any vertex $v_0$ and BFS-colour by depth parity. If two adjacent vertices got the same colour, their two paths to $v_0$ combine into a closed walk of odd length, hence contain an odd cycle — contradiction. So the colouring is proper and $G$ is bipartite. ∎
The Königsberg bridges form a multigraph on four vertices with degrees $(3, 3, 3, 5)$. Why is there no Euler path?
Show solution
Euler path exists iff $\leq 2$ odd-degree vertices. Here all four are odd, so no Euler path (and certainly no Euler circuit). ∎
Does $K_5$ have an Euler circuit? An Euler path?
Show solution
$K_5$: every vertex has degree 4 (even). Connected. So Euler circuit exists. Any Euler circuit is also an Euler path.
$K_4$: Euler circuit? path?
Show solution
Every vertex has degree 3 (odd) — four odd-degree vertices, more than 2. Neither exists.
For which $m, n$ does $K_{m,n}$ have a Hamiltonian cycle?
Show solution
Any cycle in a bipartite graph has even length and alternates sides — so visits the same number of vertices on each side. For a Hamiltonian cycle visiting all $m+n$ vertices, we need $m = n$.
When $m = n$, a Hamiltonian cycle exists: pair up vertices alternately.
Show $Q_n$ has a Hamiltonian cycle for $n \geq 2$.
Show solution
Use Gray code: a sequence of all $2^n$ $n$-bit strings where consecutive strings differ in one bit, with the last and first also differing in one bit. Standard reflected Gray code construction (induction on $n$) gives this. ∎
Describe how to find the number of connected components of a graph algorithmically.
Show solution
Run BFS or DFS from an unvisited vertex; this finds one component. Repeat from any still-unvisited vertex. Count how many such restarts you do — that's the number of components. Time $O(|V|+|E|)$.
Show: in a tree with $\geq 2$ vertices, every internal (non-leaf) vertex is a cut vertex.
Show solution
In a tree, the path between any two vertices is unique. Take internal vertex $v$ with neighbours $u, w$ in different subtrees. Removing $v$ disconnects $u$ from $w$ — they had only the path through $v$. ∎
Students $S_1, S_2, S_3, S_4$ with preferences $S_1: \{P_1, P_2\}, S_2: \{P_2, P_3\}, S_3: \{P_3, P_4\}, S_4: \{P_1, P_4\}$. Is there a perfect matching?
Show solution
Check Hall's condition for every subset of students:
- Singletons: each has 2 neighbours ≥ 1. ✓
- Pairs: $\{S_1,S_2\}$: $\{P_1,P_2,P_3\}$, size 3 ≥ 2. ✓ Similarly others.
- Triples and all four: easy to check.
Preferences change: $S_1: \{P_1\}, S_2: \{P_1\}, S_3: \{P_2, P_3\}, S_4: \{P_4\}$. Perfect matching?
Show solution
Hall's condition fails on $S = \{S_1, S_2\}$: $N(S) = \{P_1\}$, $|N(S)| = 1 < 2 = |S|$. No perfect matching. ∎
- Memorize the 5 families: $K_n, C_n, W_n, Q_n, K_{m,n}$ — vertex/edge counts and degrees.
- Handshake lemma is a quick way to derive edge counts or check feasibility of degree sequences.
- Bipartite test: 2-colourable $\iff$ no odd cycle.
- Euler: count odd-degree vertices. 0 → circuit, 2 → path, else neither.
- Hamilton: no easy test; use Dirac ($\deg \geq n/2$) or Ore ($\deg(u) + \deg(v) \geq n$) as sufficient.
- $K_{m,n}$ Hamilton iff $m = n$; bipartite cycle alternates, must have $m = n$.