Skills101

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:

  1. Sort the sequence in decreasing order and remove zeros.
  2. Take the first degree d off the list.
  3. Subtract 1 from each of the next d degrees. (The removed vertex is joined to the d vertices with the largest degrees.)
  4. 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.

Havel–Hakimi steps computed for two sequences: 3 3 2 2 2 reduces to 2 2 1 1, then 1 1 0, then 0 0, so it is graphical; 3 3 3 1 reduces to 2 2 0, then a vertex of degree 2 has only one other non-zero vertex to join, so it is not graphical even though its sum is even

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 2 is graphical (for example, a 5-cycle with one extra chord).
  • 3 3 3 1 has 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 1 fails 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

The house figure with the computed Euler path: the walk starts at C, the odd-degree corner, uses all 8 edges exactly once in the numbered order, and ends at the other odd corner D

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:

TheoremConditionThen
Dirac (1952)every vertex has degree ≥ n/2Hamiltonian
Ore (1960)deg(u) + deg(v) ≥ n for every pair of non-adjacent u, vHamiltonian

"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…BoundWhy
any simple planar graphE ≤ 3V − 6each face has at least 3 edges
no triangles (girth ≥ 4)E ≤ 2V − 4each face has at least 4 edges
shortest cycle length gE ≤ 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.

Practice what you learned

📝 Quiz: Graph Theory Workshop5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →