AdvancedDiscrete Mathematics · Lesson 10 of 10 · Updated ·
Graph Theory Workshop — Degree Sequences, Euler and Hamilton Paths, and Planarity Tests with Computed Examples
The graph theory basics lesson gave the definitions and the main theorems. This workshop uses them on real problems — the kind that appear as 5- and 10-mark questions: "Is there a simple graph with degrees 3, 3, 3, 1?", "Draw this figure without lifting your pen", "Is this graph Hamiltonian?", "Prove that this graph is not planar." For each one we solve it by reasoning and then compute the answer in Python.
1. Degree sequences: can such a graph exist?
The degree sequence of a graph is the list of all vertex degrees, usually written largest first. A sequence is graphical if some simple graph (no loops, no repeated edges) has exactly those degrees.
Two quick tests rule many sequences out:
- The sum of degrees must be even (handshaking lemma).
- No degree can be more than n − 1, where n is the number of vertices.
Passing both is not enough. The Havel–Hakimi algorithm decides it exactly:
- Sort the sequence in decreasing order and remove zeros.
- Take the first degree d off the list.
- Subtract 1 from each of the next d degrees. (The removed vertex is joined to the d vertices with the largest degrees.)
- If any degree becomes negative, or there are fewer than d degrees left, the sequence is not graphical. If everything becomes 0, it is graphical. Otherwise repeat.
def havel_hakimi(seq):
seq = sorted(seq, reverse=True)
print("start:", seq)
while True:
seq = [d for d in seq if d > 0]
if not seq:
return True
d = seq.pop(0)
if d > len(seq):
return False
for i in range(d):
seq[i] -= 1
if min(seq) < 0:
print(f"take {d}:", seq, "<- negative")
return False
seq.sort(reverse=True)
print(f"take {d}:", seq)
for s in [[3, 3, 2, 2, 2], [3, 3, 3, 1], [4, 4, 3, 1, 1]]:
print("sum =", sum(s), "| graphical:", havel_hakimi(s))
print()
start: [3, 3, 2, 2, 2]
take 3: [2, 2, 1, 1]
take 2: [1, 1, 0]
take 1: [0]
sum = 12 | graphical: True
start: [3, 3, 3, 1]
take 3: [2, 2, 0]
sum = 10 | graphical: False
start: [4, 4, 3, 1, 1]
take 4: [3, 2, 0, 0]
sum = 13 | graphical: False
3 3 2 2 2is graphical (for example, a 5-cycle with one extra chord).3 3 3 1has an even sum but is not graphical: three vertices of degree 3 in a 4-vertex graph must each touch every other vertex, so the last vertex would need degree 3, not 1.4 4 3 1 1fails immediately on the handshaking test (sum 13 is odd). Havel–Hakimi also rejects it.
Two more facts that save time:
- A k-regular graph (every vertex has degree k) on n vertices has n·k/2 edges. So a 3-regular graph on 7 vertices cannot exist (21/2 is not a whole number).
- In the complement of a simple graph (join exactly the pairs that were not joined), each degree d becomes n − 1 − d.
2. Euler paths: actually finding one
Recall the rule for a connected graph: an Euler circuit exists if every degree is even; an Euler path exists if exactly two vertices have odd degree, and it must start at one of them and end at the other.
Exams also ask you to find the path. Hierholzer's algorithm does it in O(E) time: walk along unused edges until you get stuck, then back up and splice in a detour from the last vertex that still has unused edges.
Problem: draw the "house" without lifting your pen. The house is a square A-B-C-D with both diagonals, plus a roof peak E joined to A and B.
from collections import defaultdict
def euler_path(edges):
adj = defaultdict(list)
for i, (u, v) in enumerate(edges):
adj[u].append((v, i))
adj[v].append((u, i))
odd = sorted(v for v in adj if len(adj[v]) % 2)
print("degrees:", {v: len(adj[v]) for v in sorted(adj)}, "| odd:", odd)
if len(odd) not in (0, 2):
return None
start = odd[0] if odd else sorted(adj)[0]
used = [False] * len(edges)
stack, path = [start], []
while stack:
u = stack[-1]
while adj[u] and used[adj[u][-1][1]]:
adj[u].pop() # drop edges already walked
if adj[u]:
v, i = adj[u].pop()
used[i] = True
stack.append(v) # walk forward
else:
path.append(stack.pop()) # stuck: this vertex is finished
return path[::-1]
house = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A"), ("A", "C"), ("B", "D"), ("A", "E"), ("B", "E")]
route = euler_path(house)
print("route:", " -> ".join(route), "|", len(route) - 1, "edges")
konigsberg = [("A", "B"), ("A", "B"), ("A", "C"), ("A", "C"), ("A", "D"), ("B", "D"), ("C", "D")]
print("Konigsberg:", euler_path(konigsberg))
degrees: {'A': 4, 'B': 4, 'C': 3, 'D': 3, 'E': 2} | odd: ['C', 'D']
route: C -> A -> E -> B -> D -> A -> B -> C -> D | 8 edges
degrees: {'A': 5, 'B': 3, 'C': 3, 'D': 3} | odd: ['A', 'B', 'C', 'D']
Konigsberg: None
Exactly two vertices (C and D) have odd degree, so the route must start at one and end at the other. The Königsberg bridges graph (multiple edges allowed) has four odd vertices, so the function returns None: no walk crosses each bridge exactly once.
3. Hamiltonian cycles: sufficient tests and their limits
There is no simple "if and only if" test for a Hamiltonian cycle (a cycle through every vertex exactly once). There are two well-known sufficient conditions for a simple graph with n ≥ 3 vertices:
| Theorem | Condition | Then |
|---|---|---|
| Dirac (1952) | every vertex has degree ≥ n/2 | Hamiltonian |
| Ore (1960) | deg(u) + deg(v) ≥ n for every pair of non-adjacent u, v | Hamiltonian |
"Sufficient" means: if the condition holds, a Hamiltonian cycle definitely exists. If it fails, you learn nothing. A plain 6-cycle fails both tests (every degree is 2 < 3) and is obviously Hamiltonian.
The famous counterexample in the other direction is the Petersen graph: 10 vertices, every degree 3, highly symmetric — and no Hamiltonian cycle. Since there is no shortcut test, we prove it by a complete backtracking search:
def dirac(adj):
n = len(adj)
return all(len(adj[v]) >= n / 2 for v in adj)
def ore(adj):
n = len(adj)
return all(len(adj[u]) + len(adj[v]) >= n for u in adj for v in adj if u != v and v not in adj[u])
def hamiltonian_cycle(adj):
vs = sorted(adj)
n, start = len(vs), vs[0]
path, seen = [start], {start}
def extend():
if len(path) == n:
return start in adj[path[-1]]
for w in sorted(adj[path[-1]]):
if w not in seen:
path.append(w); seen.add(w)
if extend():
return True
path.pop(); seen.discard(w)
return False
return path + [start] if extend() else None
def graph(edges):
adj = {}
for u, v in edges:
adj.setdefault(u, set()).add(v)
adj.setdefault(v, set()).add(u)
return adj
c6 = graph([(i, (i + 1) % 6) for i in range(6)])
k33 = graph([(a, b) for a in "abc" for b in "xyz"])
petersen = graph([(i, (i + 1) % 5) for i in range(5)] + # outer 5-cycle
[(5 + i, 5 + (i + 2) % 5) for i in range(5)] + # inner star
[(i, i + 5) for i in range(5)]) # spokes
for name, g in [("C6", c6), ("K3,3", k33), ("Petersen", petersen)]:
print(f"{name:8} n={len(g):2} Dirac={dirac(g)!s:5} Ore={ore(g)!s:5} cycle={hamiltonian_cycle(g)}")
C6 n= 6 Dirac=False Ore=False cycle=[0, 1, 2, 3, 4, 5, 0]
K3,3 n= 6 Dirac=True Ore=True cycle=['a', 'x', 'b', 'y', 'c', 'z', 'a']
Petersen n=10 Dirac=False Ore=False cycle=None
- K₃,₃ satisfies Dirac (degree 3 ≥ 6/2), and the search finds a cycle, as the theorem promised.
- C₆ fails both tests but is Hamiltonian — the tests are one-way.
- The Petersen graph fails both tests, and the search tries every possibility and finds no cycle.
The search is exponential in the worst case. That is expected: deciding whether a graph is Hamiltonian is NP-complete (see the decidability lesson in Theory of Computation).
4. Proving a graph is not planar
For a connected simple planar graph with V ≥ 3 vertices, Euler's formula V − E + F = 2 leads to edge limits:
| Graph has… | Bound | Why |
|---|---|---|
| any simple planar graph | E ≤ 3V − 6 | each face has at least 3 edges |
| no triangles (girth ≥ 4) | E ≤ 2V − 4 | each face has at least 4 edges |
| shortest cycle length g | E ≤ g(V − 2)/(g − 2) | each face has at least g edges |
If a graph has more edges than the bound, it is not planar. If it is within the bound, the test says nothing — you then need a drawing (to show planar) or Kuratowski's theorem (to show non-planar).
from collections import deque
def girth(adj): # length of the shortest cycle (BFS from every vertex)
best = float("inf")
for s in adj:
dist, parent, q = {s: 0}, {s: None}, deque([s])
while q:
u = q.popleft()
for w in adj[u]:
if w not in dist:
dist[w], parent[w] = dist[u] + 1, u
q.append(w)
elif parent[u] != w:
best = min(best, dist[u] + dist[w] + 1)
return best
def graph(edges):
adj = {}
for u, v in edges:
adj.setdefault(u, set()).add(v)
adj.setdefault(v, set()).add(u)
return adj
graphs = {
"K4": graph([(a, b) for a in range(4) for b in range(a + 1, 4)]),
"K5": graph([(a, b) for a in range(5) for b in range(a + 1, 5)]),
"K3,3": graph([(a, b) for a in "abc" for b in "xyz"]),
"cube Q3": graph([(a, a ^ (1 << k)) for a in range(8) for k in range(3) if a < a ^ (1 << k)]),
"Petersen": graph([(i, (i + 1) % 5) for i in range(5)] + [(5 + i, 5 + (i + 2) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]),
}
for name, g in graphs.items():
V, E, gi = len(g), sum(len(n) for n in g.values()) // 2, girth(g)
bound = gi * (V - 2) / (gi - 2)
verdict = "NOT planar" if E > bound else "bound passed (no conclusion)"
print(f"{name:8} V={V:2} E={E:2} girth={gi} bound={bound:5.2f} -> {verdict}")
K4 V= 4 E= 6 girth=3 bound= 6.00 -> bound passed (no conclusion)
K5 V= 5 E=10 girth=3 bound= 9.00 -> NOT planar
K3,3 V= 6 E= 9 girth=4 bound= 8.00 -> NOT planar
cube Q3 V= 8 E=12 girth=4 bound=12.00 -> bound passed (no conclusion)
Petersen V=10 E=15 girth=5 bound=13.33 -> NOT planar
- K₅ breaks E ≤ 3V − 6 (10 > 9) and K₃,₃ breaks E ≤ 2V − 4 (9 > 8): the two classic non-planar graphs.
- The Petersen graph has no cycle shorter than 5, so E ≤ 5(V − 2)/3 = 13.33, but it has 15 edges: not planar.
- K₄ and the cube pass their bounds. That alone proves nothing, but both can be drawn without crossings, so they are planar. For the cube, Euler's formula then gives F = 2 − V + E = 2 − 8 + 12 = 6 faces — the six faces of a cube.
Common mistakes
- Saying a sequence is graphical because its sum is even. Run Havel–Hakimi (3 3 3 1 has an even sum and is not graphical).
- Starting an Euler path at an even-degree vertex when two vertices are odd. It must start at an odd one.
- Treating Dirac or Ore as "if and only if". Failing them does not mean the graph is non-Hamiltonian.
- Using E ≤ 3V − 6 to prove a graph is planar. The bound can only prove non-planarity.
- Using E ≤ 3V − 6 for K₃,₃ (9 ≤ 12 passes). It has no triangles, so use E ≤ 2V − 4.
Quick recap
- Degree sequences: even sum and max degree ≤ n − 1 are necessary; Havel–Hakimi decides exactly.
- k-regular on n vertices has nk/2 edges; complement degrees are n − 1 − d.
- Euler path: 0 or 2 odd vertices; find it with Hierholzer's algorithm in O(E), starting at an odd vertex.
- Dirac (deg ≥ n/2) and Ore (deg u + deg v ≥ n for non-adjacent pairs) guarantee a Hamiltonian cycle; the Petersen graph is 3-regular with none.
- Non-planarity: E > 3V − 6, or E > 2V − 4 without triangles, or E > g(V − 2)/(g − 2) in general.