Graphs: connectivity, Euler tours and Hamilton cycles

The second half of the course turns from counting to structure. MATH-260 introduced graphs, components, bridges, Euler's theorem with Hierholzer's algorithm, Hamilton cycles and Dirac's theorem. This lesson revisits these ideas at greater depth. It measures how well connected a graph is, describes how 2-connected graphs are built, extends Euler's theorem to directed graphs and de Bruijn sequences, and proves Ore's sufficient condition for Hamilton cycles, while explaining why no simple characterization of Hamiltonian graphs is expected.

Throughout, a graph \(G = (V, E)\) is finite and simple unless stated otherwise; \(n = |V|\), \(\delta(G)\) is the minimum degree and \(\Delta(G)\) the maximum degree. A multigraph allows repeated edges and loops, and a directed graph has ordered pairs as edges.

Euler's problem revisited

In 1736 Leonhard Euler considered the city of Königsberg, whose four land masses were joined by seven bridges, and asked whether a walk could cross each bridge exactly once. He saw that only the pattern of connections matters, which in modern terms is a multigraph with a vertex for each land mass and an edge for each bridge.

Theorem (Euler; Hierholzer 1873). A connected multigraph has a closed walk using every edge exactly once if and only if every vertex has even degree. It has an open walk using every edge exactly once if and only if exactly two vertices have odd degree, and the walk then runs between them.

Necessity is the parity argument: a closed trail leaves every vertex as often as it enters. MATH-260 proved sufficiency with Hierholzer's algorithm: walk until stuck, which can only happen at the start; then splice in closed detours from vertices with unused edges. In Königsberg all four degrees are odd, so no such walk exists. Carl Hierholzer's proof was published posthumously in 1873; Euler had stated the condition but proved only necessity.

Directed version. A connected directed multigraph has a directed closed walk using every arc exactly once if and only if every vertex has in-degree equal to out-degree. The proof is the same, with arcs followed only forwards. One application is the de Bruijn sequence. Take the directed graph whose vertices are the binary strings of length \(k - 1\), with an arc from \(a_1\cdots a_{k-1}\) to \(a_2\cdots a_k\) labelled \(a_k\) for every string \(a_1 \cdots a_k\). Every vertex has in-degree and out-degree 2, so an Euler circuit exists, and reading its labels gives a cyclic sequence of length \(2^k\) in which every binary string of length \(k\) occurs exactly once as a window. For \(k = 3\) one such sequence is 00010111. Nicolaas de Bruijn published the construction and counted such sequences in 1946; Camille Flye Sainte-Marie had found the count in 1894. These sequences are used to test keypads and to locate a position from a short window of a pattern in robotics and imaging.

The Chinese postman problem asks for the shortest closed walk using every edge at least once, as a letter carrier must. Kwan Mei-Ko posed it in 1962. If the graph is not Eulerian, some edges must be repeated; the optimal choice pairs up the odd-degree vertices so as to minimize the total length of the shortest paths between partners, a matching problem of the kind solved in lesson 10. Jack Edmonds and Ellis Johnson gave a polynomial-time algorithm in 1973.

Measuring connectivity

A connected graph may be fragile or robust. A cut vertex is one whose removal disconnects the graph, and a bridge is an edge whose removal does. More generally, the vertex connectivity \(\kappa(G)\) is the smallest number of vertices whose removal disconnects \(G\) or leaves a single vertex, and the edge connectivity \(\lambda(G)\) is the smallest number of edges whose removal disconnects \(G\). A graph is \(k\)-connected if \(\kappa(G) \ge k\), and \(k\)-edge-connected if \(\lambda(G) \ge k\).

Theorem (Whitney, 1932). For every graph, \(\kappa(G) \le \lambda(G) \le \delta(G)\).

Proof. Removing all edges at a vertex of minimum degree isolates it, so \(\lambda \le \delta\). For \(\kappa \le \lambda\), let \(F\) be a minimum disconnecting set of edges, splitting the vertices into sides \(S\) and \(\bar{S}\). If every vertex of \(S\) is adjacent to every vertex of \(\bar{S}\), then \(|F| = |S||\bar{S}| \ge n - 1 \ge \kappa\). Otherwise pick \(x \in S\) and \(y \in \bar{S}\) not adjacent. For each edge of \(F\), remove its endpoint in \(S\) unless that endpoint is \(x\), in which case remove its endpoint in \(\bar{S}\). At most \(|F|\) vertices are removed, \(x\) and \(y\) survive, and every path from \(x\) to \(y\) used an edge of \(F\), all of which are now gone. So \(\kappa \le |F| = \lambda\).

Both inequalities can be strict. Two copies of \(K_4\) sharing a single vertex have \(\kappa = 1\), \(\lambda = 3\) and \(\delta = 3\). Lesson 11 proves Menger's theorem, the deep fact behind connectivity: a graph is \(k\)-connected exactly when every two vertices are joined by \(k\) paths sharing no internal vertex.

Blocks and 2-connected graphs

A block of a graph is a maximal connected subgraph without a cut vertex of its own: either a bridge with its two ends, an isolated vertex, or a maximal 2-connected subgraph. Two blocks share at most one vertex, which is then a cut vertex of the whole graph. The block–cutpoint graph, with a node for each block and each cut vertex and an edge when the cut vertex lies in the block, is a tree. So every connected graph is a tree of blocks, and many questions reduce to 2-connected graphs.

Theorem (Whitney). A graph with at least three vertices is 2-connected if and only if every two vertices lie on a common cycle. Equivalently, it has an ear decomposition: it can be built from a cycle by repeatedly adding a path, called an ear, whose two ends are distinct vertices already present and whose interior vertices are new.

Sketch. Adding an ear to a 2-connected graph cannot create a cut vertex, because the two ends of the ear are joined by the ear and by a path in the old graph, so the proof of sufficiency is by induction. Conversely, in a 2-connected graph start with any cycle \(H\). If \(H \ne G\), some edge \(uv\) leaves \(H\) or joins two vertices of \(H\) by a chord; since \(G - u\) is connected, there is a path from \(v\) back to \(H\) avoiding \(u\), and \(u\), \(v\) and this path form an ear. Ear decompositions underlie efficient algorithms for testing 2-connectivity and planarity. In practice, cut vertices and blocks are found in linear time by depth-first search, using the low-point values introduced by Hopcroft and Tarjan in 1973, as the program below does.

Hamilton cycles

A Hamilton cycle visits every vertex exactly once. William Rowan Hamilton marketed the Icosian game in 1857, which asked for such a cycle along the edges of a dodecahedron; Thomas Kirkman had studied the question for polyhedra a little earlier. Superficially like the Euler problem, the Hamilton problem is profoundly harder: deciding whether a graph has a Hamilton cycle is NP-complete, one of the 21 problems in Richard Karp's 1972 list. So no efficient characterization is expected, and the theory consists of sufficient conditions and necessary conditions.

A necessary condition. If \(G\) has a Hamilton cycle \(C\), then removing any set \(S\) of \(k\) vertices leaves at most \(k\) components, since removing \(k\) vertices from the cycle \(C\) leaves at most \(k\) paths, and \(G - S\) contains those paths as spanning subgraphs. For example \(K_{2,3}\) is not Hamiltonian: removing its two-vertex side leaves three isolated vertices. The Petersen graph satisfies this condition yet has no Hamilton cycle, as the program confirms by exhaustive search, so the condition is not sufficient.

Theorem (Ore, 1960). Let \(G\) have \(n \ge 3\) vertices, and suppose \(\deg u + \deg v \ge n\) for every pair of nonadjacent vertices \(u, v\). Then \(G\) has a Hamilton cycle.

Proof. Suppose not, and add edges to \(G\) while the condition remains true and no Hamilton cycle appears; adding edges preserves the condition. We reach a graph \(G'\) with no Hamilton cycle such that adding any missing edge \(uv\) creates one. That cycle uses the edge \(uv\), so \(G'\) has a Hamilton path \(u = v_1, v_2, \ldots, v_n = v\). Let \(A = \{i : v_1v_{i+1} \in E\}\) and \(B = \{i : v_iv_n \in E\}\), subsets of \(\{1, \ldots, n - 1\}\). Since \(|A| + |B| = \deg u + \deg v \ge n > n - 1\), some \(i\) lies in both. Then \(v_1, v_2, \ldots, v_i, v_n, v_{n-1}, \ldots, v_{i+1}, v_1\) is a Hamilton cycle in \(G'\), a contradiction.

Corollary (Dirac, 1952). If \(\delta(G) \ge n/2\) and \(n \ge 3\), then \(G\) is Hamiltonian. The bound is sharp: \(K_{m, m+1}\) has minimum degree \(m = (n - 1)/2\) and no Hamilton cycle, since a cycle in a bipartite graph alternates sides and needs equal sides. The idea of the proof was distilled by Bondy and Chvátal in 1976 into the closure: repeatedly joining nonadjacent vertices whose degree sum is at least \(n\) does not change whether a graph is Hamiltonian.

Tournaments. A tournament is a directed graph with exactly one arc between each pair of vertices, recording who beat whom in a round-robin. László Rédei proved in 1934 that every tournament has a directed Hamilton path, so the players can always be listed so that each beat the next. The proof is by insertion: given a path through some players, a new player \(x\) can be placed at the front if \(x\) beat the first, at the end if the last beat \(x\), and otherwise between the first consecutive pair \(v_i \to v_{i+1}\) with \(v_i\) beating \(x\) and \(x\) beating \(v_{i+1}\), which must exist.

from itertools import product

def components(adj):
    seen, comps = set(), []
    for s in adj:
        if s in seen:
            continue
        comp, stack = [], [s]; seen.add(s)
        while stack:
            u = stack.pop(); comp.append(u)
            for w in adj[u]:
                if w not in seen:
                    seen.add(w); stack.append(w)
        comps.append(sorted(comp))
    return comps

def cut_vertices(adj):
    disc, low, cuts, t = {}, {}, set(), [0]
    def dfs(u, parent):
        disc[u] = low[u] = t[0]; t[0] += 1
        children = 0
        for w in adj[u]:
            if w not in disc:
                children += 1
                dfs(w, u)
                low[u] = min(low[u], low[w])
                if parent is not None and low[w] >= disc[u]:
                    cuts.add(u)
            elif w != parent:
                low[u] = min(low[u], disc[w])
        if parent is None and children > 1:
            cuts.add(u)
    for s in adj:
        if s not in disc:
            dfs(s, None)
    return sorted(cuts)

def graph(edges):
    adj = {}
    for a, b in edges:
        adj.setdefault(a, []).append(b); adj.setdefault(b, []).append(a)
    return adj

bowtie = graph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 5), (5, 3), (6, 7)])
print("components:", components(bowtie), " cut vertices:", cut_vertices(bowtie))

def euler_circuit(arcs, start):
    out = {}
    for a, b, lab in arcs:
        out.setdefault(a, []).append((b, lab))
    stack, path = [(start, None)], []
    while stack:
        v, lab = stack[-1]
        if out.get(v):
            w, l2 = out[v].pop()
            stack.append((w, l2))
        else:
            stack.pop(); path.append(lab)
    return [l for l in reversed(path) if l is not None]

def de_bruijn(k):
    arcs = []
    for bits in product("01", repeat=k):
        word = "".join(bits)
        arcs.append((word[:-1], word[1:], word[-1]))
    return "".join(euler_circuit(arcs, "0" * (k - 1)))

for k in [3, 4]:
    seq = de_bruijn(k)
    windows = {(seq + seq[:k - 1])[i:i + k] for i in range(len(seq))}
    print(f"de Bruijn k={k}: {seq}  length {len(seq)}, distinct windows {len(windows)}")

def hamilton_cycle(adj, n):
    path, used = [0], {0}
    def extend():
        if len(path) == n:
            return 0 in adj[path[-1]]
        for w in adj[path[-1]]:
            if w not in used:
                path.append(w); used.add(w)
                if extend():
                    return True
                path.pop(); used.discard(w)
        return False
    return path[:] if extend() else None

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)])
print("Petersen graph Hamilton cycle:", hamilton_cycle(petersen, 10))
dodeca_edges = [(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)] + \
    [(5 + i, 10 + i) for i in range(5)] + [(5 + i, 10 + (i - 1) % 5) for i in range(5)] + \
    [(10 + i, 15 + i) for i in range(5)] + [(15 + i, 15 + (i + 1) % 5) for i in range(5)]
dodeca = graph(dodeca_edges)
print("dodecahedron degrees all 3:", all(len(v) == 3 for v in dodeca.values()), " edges:", len(dodeca_edges))
print("dodecahedron Hamilton cycle:", hamilton_cycle(dodeca, 20))

def ore_holds(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])
k33 = graph([(a, b) for a in range(3) for b in range(3, 6)])
k34 = graph([(a, b) for a in range(3) for b in range(3, 7)])
print("K3,3: Ore holds", ore_holds(k33), " cycle", hamilton_cycle(k33, 6))
print("K3,4: Ore holds", ore_holds(k34), " cycle", hamilton_cycle(k34, 7))

import random
random.seed(1934)
n = 8
beats = {(i, j) if random.random() < 0.5 else (j, i) for i in range(n) for j in range(i + 1, n)}
order = []
for x in range(n):
    if not order or (x, order[0]) in beats:
        order.insert(0, x)
    elif (order[-1], x) in beats:
        order.append(x)
    else:
        i = next(i for i in range(len(order) - 1) if (order[i], x) in beats and (x, order[i + 1]) in beats)
        order.insert(i + 1, x)
print("tournament Hamilton path:", order, " valid:", all((order[i], order[i + 1]) in beats for i in range(n - 1)))

components: [[1, 2, 3, 4, 5], [6, 7]]  cut vertices: [3]
de Bruijn k=3: 11101000  length 8, distinct windows 8
de Bruijn k=4: 1111011001010000  length 16, distinct windows 16
Petersen graph Hamilton cycle: None
dodecahedron degrees all 3: True  edges: 30
dodecahedron Hamilton cycle: [0, 1, 2, 3, 4, 9, 14, 19, 15, 16, 17, 18, 13, 8, 12, 7, 11, 6, 10, 5]
K3,3: Ore holds True  cycle [0, 3, 1, 4, 2, 5]
K3,4: Ore holds False  cycle None
tournament Hamilton path: [7, 6, 5, 3, 4, 2, 0, 1]  valid: True

The bowtie graph has its shared vertex as the only cut vertex. Hierholzer's algorithm on the de Bruijn graph produces sequences in which every window of length \(k\) appears exactly once. Exhaustive search finds no Hamilton cycle in the Petersen graph but finds one quickly in the dodecahedron, Hamilton's original puzzle. \(K_{3,3}\) satisfies Ore's condition and is Hamiltonian, while \(K_{3,4}\) fails it and has no Hamilton cycle. Insertion builds a Hamilton path through a random tournament.