Paths, connectivity, Euler and Hamilton

Networks exist so that things can travel through them: messages through the internet, cars along roads, electricity along power lines. The basic questions about a network are therefore questions about routes. Can every vertex reach every other? Which edges, if they failed, would cut the network in two? Is there a route that uses every edge exactly once, as a snow-clearing crew or a postal carrier would like, or one that visits every vertex exactly once, as a delivery driver would? The first two questions have clean answers that are easy to compute. The Euler question, about edges, has a complete and beautiful answer that goes back to 1736. The Hamilton question, about vertices, sounds almost the same but is one of the hardest problems in computer science.

Walks, trails, paths and cycles

Lesson 7 defined a walk as a sequence of vertices \(v_0, v_1, \dots, v_k\) with each consecutive pair adjacent; its length is \(k\), the number of edges used. Three restricted kinds of walk matter. A trail is a walk that does not repeat an edge. A path is a walk that does not repeat a vertex, and therefore does not repeat an edge either. A walk is closed if it ends where it starts; a closed trail is called a circuit, and a cycle is a closed walk of length at least 3 that repeats no vertex except that the first and last are equal.

Lemma. If there is a walk from \(u\) to \(v\), there is a path from \(u\) to \(v\). Proof: take a walk from \(u\) to \(v\) of the smallest possible length. If it repeated a vertex, say \(v_i = v_j\) with \(i < j\), then cutting out the part between positions \(i\) and \(j\) would leave a shorter walk from \(u\) to \(v\), contradicting minimality. So the shortest walk repeats no vertex and is a path.

Connectivity

A graph is connected if there is a path between every pair of vertices. In any graph, say \(u \sim v\) when there is a path from \(u\) to \(v\). This relation is reflexive, symmetric and transitive, the last because a path from \(u\) to \(v\) followed by one from \(v\) to \(w\) is a walk from \(u\) to \(w\), which contains a path by the lemma. So \(\sim\) is an equivalence relation, and its equivalence classes are the connected components of the graph: the maximal connected pieces. A graph is connected exactly when it has one component.

Components are found by graph search. Breadth-first search (BFS) starts at a vertex, visits all its neighbours, then all their unvisited neighbours, and so on, layer by layer. Depth-first search (DFS) follows one route as far as possible before backing up. Either search started at \(v\) visits exactly the vertices of the component containing \(v\). Repeating from an unvisited vertex until none is left finds every component, in time proportional to \(n + m\) with adjacency lists.

How many edges must a connected graph have? At least \(n - 1\). One way to see this: start with the \(n\) vertices and no edges, which form \(n\) components, and add the edges one at a time. Each edge either joins two different components into one, reducing the number of components by 1, or lies within a component and changes nothing. To get down to one component we need at least \(n - 1\) edges. Lesson 9 shows that connected graphs with exactly \(n - 1\) edges are the trees.

An edge whose removal increases the number of components is a bridge, or cut edge; a vertex whose removal does so is a cut vertex. Theorem: an edge is a bridge exactly when it lies on no cycle. If \(uv\) lies on a cycle, removing it still leaves the rest of the cycle as a route from \(u\) to \(v\), so nothing is disconnected. If \(uv\) lies on no cycle, then after removing it there is no path from \(u\) to \(v\), since such a path together with the edge would form a cycle. Network designers avoid bridges: a single failure on a bridge splits the network.

Bipartite graphs and odd cycles

Theorem. A graph is bipartite if and only if it has no cycle of odd length.

Proof. Suppose \(G\) is bipartite with parts \(X\) and \(Y\). Along any cycle the vertices alternate between \(X\) and \(Y\), and to return to the starting side the cycle must take an even number of steps. So every cycle has even length.

Conversely, suppose \(G\) has no odd cycle. It is enough to treat each component separately, so assume \(G\) is connected. Fix a vertex \(r\), let \(X\) be the vertices at even distance from \(r\) and \(Y\) those at odd distance, where distance means the length of a shortest path. Suppose some edge \(uv\) had both ends in \(X\), or both in \(Y\). Take shortest paths from \(r\) to \(u\) and from \(r\) to \(v\); their lengths have the same parity. Let \(w\) be the last vertex the two paths share. The parts of the two paths from \(w\) to \(u\) and from \(w\) to \(v\), together with the edge \(uv\), form a cycle whose length is the sum of two numbers of the same parity, plus 1, which is odd. This contradicts the assumption, so every edge goes between \(X\) and \(Y\) and \(G\) is bipartite.

The proof is also an algorithm: run BFS from any vertex, put each layer alternately on the two sides, and check whether some edge joins two vertices of the same layer parity. If one does, the graph contains an odd cycle and is not bipartite.

Euler circuits and trails

An Euler trail uses every edge of a graph exactly once; an Euler circuit is an Euler trail that returns to its start. These may be multigraphs, as Königsberg was. Euler's insight was that only the degrees matter.

Theorem. A connected multigraph has an Euler circuit if and only if every vertex has even degree. It has an Euler trail that is not a circuit if and only if exactly two vertices have odd degree, and then the trail starts at one of them and ends at the other.

Proof that the condition is necessary. Follow an Euler circuit. Each time it passes through a vertex it arrives along one edge and leaves along another, using two edges at that vertex; the start and end, being the same vertex, also pair up. Since every edge is used exactly once, the edges at each vertex are paired off, so every degree is even. For an Euler trail from \(a\) to \(b\) with \(a \ne b\), the same argument pairs up the edges at every vertex except \(a\) and \(b\), which each have one unpaired edge.

Proof that the condition is sufficient. Suppose every degree is even and the graph is connected. Start at any vertex and walk along unused edges, never reusing one, until you cannot continue. Because every degree is even, whenever the walk enters a vertex other than the start it can leave again; so it can only get stuck at the start, and it has produced a closed trail. If this trail uses every edge, we are done. If not, some vertex \(v\) on the trail has an unused edge, because the graph is connected. Removing the trail's edges leaves every degree even, so from \(v\) we can build another closed trail from unused edges and splice it into the first one at \(v\). Repeating, we eventually use every edge. This construction is Hierholzer's algorithm, published in 1873. For the trail case, add an extra edge between the two odd vertices, find an Euler circuit, and delete the extra edge.

For Königsberg, all four land masses had odd degree, 3, 3, 3 and 5, so no Euler trail exists. The children's puzzle of drawing a figure without lifting the pencil or retracing a line is the same question: it can be done exactly when the figure has 0 or 2 points where an odd number of lines meet. In practice the theorem underlies route planning for street sweepers and snow-clearing crews. When a network has odd vertices, the cheapest tour must repeat some edges, and the Chinese postman problem asks which; its solution pairs up the odd vertices as cheaply as possible.

Hamilton paths and cycles

A Hamilton path visits every vertex exactly once; a Hamilton cycle does so and returns to the start. They are named after William Rowan Hamilton, who in 1857 marketed a puzzle, the Icosian game, that asked for such a cycle along the edges of a dodecahedron. The question looks like the Euler question with vertices in place of edges, but no simple test like Euler's degree condition is known, and there are good reasons to think none exists. Deciding whether a graph has a Hamilton cycle is NP-complete, meaning that a fast general algorithm for it would give fast algorithms for thousands of other hard problems. Whether such algorithms exist is the P versus NP question, one of the major open problems of mathematics.

What we do have are sufficient conditions, which guarantee a Hamilton cycle when they hold but say nothing when they fail. The best known is Dirac's theorem of 1952: a graph with \(n \ge 3\) vertices in which every vertex has degree at least \(n/2\) has a Hamilton cycle. Dense graphs are therefore Hamiltonian. There are also simple obstacles. A graph with a cut vertex has no Hamilton cycle, since the cycle would have to pass through the cut vertex twice. A bipartite graph with parts of different sizes has none, since a Hamilton cycle alternates sides and so uses equally many vertices from each.

The travelling salesman problem adds costs: given distances between cities, find the shortest Hamilton cycle. It is at least as hard as the Hamilton cycle problem, yet it is solved in practice for instances with tens of thousands of cities by clever methods that avoid checking all \((n - 1)!/2\) possible tours. For small graphs, brute force is fine, as the code below shows.

from collections import deque
from itertools import permutations

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

def bipartite(adj):
    side = {}
    for s in adj:
        if s in side:
            continue
        side[s] = 0; queue = deque([s])
        while queue:
            u = queue.popleft()
            for w in adj[u]:
                if w not in side:
                    side[w] = 1 - side[u]; queue.append(w)
                elif side[w] == side[u]:
                    return False
    return True

def euler_circuit(edges, start):
    # Hierholzer's algorithm on a multigraph given as a list of edges
    adj = {}
    for i, (u, v) in enumerate(edges):
        adj.setdefault(u, []).append((v, i)); adj.setdefault(v, []).append((u, i))
    used, stack, circuit = set(), [start], []
    while stack:
        u = stack[-1]
        while adj[u] and adj[u][-1][1] in used:
            adj[u].pop()
        if adj[u]:
            v, i = adj[u].pop(); used.add(i); stack.append(v)
        else:
            circuit.append(stack.pop())
    return circuit[::-1]

def hamilton_cycle(adj):
    vs = list(adj)
    first = vs[0]
    for perm in permutations(vs[1:]):
        cyc = [first, *perm]
        if all(cyc[(i + 1) % len(cyc)] in adj[cyc[i]] for i in range(len(cyc))):
            return cyc
    return None

g = {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3], 5: []}
print("components:", components(g))
c6 = {i: [(i - 1) % 6, (i + 1) % 6] for i in range(6)}
c5 = {i: [(i - 1) % 5, (i + 1) % 5] for i in range(5)}
print("C6 bipartite:", bipartite(c6), " C5 bipartite:", bipartite(c5))

k5_edges = [(u, v) for u in range(5) for v in range(u + 1, 5)]
print("Euler circuit of K5:", euler_circuit(k5_edges, 0))

outer = [(i, (i + 1) % 5) for i in range(5)]
spokes = [(i, i + 5) for i in range(5)]
inner = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
petersen = {v: [] for v in range(10)}
for u, v in outer + spokes + inner:
    petersen[u].append(v); petersen[v].append(u)
print("Petersen graph Hamilton cycle:", hamilton_cycle(petersen))
cube = {v: [v ^ 1, v ^ 2, v ^ 4] for v in range(8)}
print("cube Q3 Hamilton cycle:", hamilton_cycle(cube))

components: [[0, 1, 2], [3, 4], [5]]
C6 bipartite: True  C5 bipartite: False
Euler circuit of K5: [0, 4, 3, 2, 4, 1, 3, 0, 2, 1, 0]
Petersen graph Hamilton cycle: None
cube Q3 Hamilton cycle: [0, 1, 3, 2, 6, 7, 5, 4]

The cube's Hamilton cycle, read as bit strings, lists all eight 3-bit strings so that consecutive strings differ in one bit. Such a listing is called a Gray code, after Frank Gray, who patented its use in 1953; Gray codes are used in rotary position sensors, where changing one bit at a time prevents large reading errors as the sensor moves.