Existence Theorems for Hamiltonian Cycles¶

Algorithm for Finding Hamiltonian Cycles¶

The following algorithm uses backtracking to find a Hamiltonian cycle in a graph:

def find_hamiltonian_cycle(graph):
    # The following algorithm finds a Hamiltonian cycle:
    n = len(graph)
    cycle = []
    visited = [False] * n

    def dfs(v):
        # Add the current vertex to the cycle
        cycle.append(v)
        visited[v] = True
        if len(cycle) == n:
            # Check if the last vertex is connected to the first
            if graph[cycle[-1]][cycle[0]] == 1:
                return cycle
            else:
                cycle.pop()
                visited[v] = False
                return None
        for u in range(n):
            if graph[v][u] == 1 and not visited[u]:
                result = dfs(u)
                if result:
                    return result
        cycle.pop()
        visited[v] = False
        return None

    return dfs(0)

Note:

The efficiency of this algorithm depends heavily on the graph's structure. For graphs meeting Chvásal's conditions, the average runtime is polynomial.

Basic Lemma¶

Consider a simple graph \(G\) with \(n\) vertices, containing two non-adjacent vertices \(a\) and \(b\) such that \(d_a + d_b \geq n\). Now consider the graph \(H\), which is the same as \(G\) but with an edge connecting vertices \(a\) and \(b\). We claim that \(G\) has a Hamiltonian cycle if and only if \(H\) has a Hamiltonian cycle.

Forward Direction: The proof of the forward direction is straightforward. If \(G\) has a Hamiltonian cycle, then \(H\) will also contain that cycle (since no edges were removed).

Reverse Direction: For the reverse direction, assume \(H\) has a Hamiltonian cycle. If this cycle does not use the edge \(ab\), then \(G\) also contains the same cycle, and the claim is proven. Thus, assume the cycle uses the edge \(ab\). Consequently, there must exist a Hamiltonian path in \(G\) starting at \(a\) and ending at \(b\).

Suppose our Hamiltonian path is \(a = v_1, v_2, \ldots, v_n = b\). If \(v_1\) is adjacent to \(v_i\) and \(v_n\) is adjacent to \(v_{i-1}\), then we can construct a Hamiltonian cycle in \(G\) as follows: move from \(v_1\) directly to \(v_i\), follow the path from \(v_i\) to \(v_n\), then move directly from \(v_n\) to \(v_{i-1}\), and finally follow the path from \(v_{i-1}\) back to \(v_1\).

Coloring Argument: For every vertex \(v_i\) adjacent to \(v_1\), color \(v_{i-1}\) red. For every vertex \(v_i\) adjacent to \(v_n\), color \(v_i\) blue. If we can prove there exists a vertex colored both red and blue, the problem is solved. By assumption, \(d_a + d_b \geq n\), so the total number of colored vertices is at least \(n\). However, the vertex \(v_n\) is never colored (why?). Thus, we have \(n-1\) vertices colored at least \(n\) times. By the pigeonhole principle, at least one vertex is colored twice. Therefore, there exists a vertex that is both red and blue, implying the existence of a Hamiltonian cycle in \(G\).

Other Theorems¶

Here we present several theorems that you can easily prove using the fundamental lemma stated earlier.

• If in graph \(G\) the degree of each vertex is at least \(\frac{n}{2}\), then this graph contains a Hamiltonian cycle.

• If in graph \(G\) for every pair of non-adjacent vertices \(a\) and \(b\) we have \(d_a + d_b \geq n\), then this graph contains a Hamiltonian cycle.