Find a Hamiltonian cycle in an undirected graph using backtracking.
Write a function `hamiltonian_cycle(n: int, edges: list[tuple[int, int]]) -> list[int] | None` that takes the number of vertices `n` (vertices are labeled 0 to n-1) and a list of undirected edges, and returns a Hamiltonian cycle as a list of vertices starting from vertex 0, where consecutive vertices are connected by an edge and the last vertex connects back to vertex 0. If no Hamiltonian cycle exists, return `None`.
A Hamiltonian cycle visits every vertex exactly once and returns to the starting vertex. The graph is undirected and simple (no self-loops, no multiple edges). The returned list should have length `n` and contain each vertex exactly once, with `cycle[0] == 0`, and every adjacent pair `(cycle[i], cycle[i+1])` and `(cycle[-1], cycle[0])` must be an edge in the graph. A Hamiltonian cycle requires at least 3 vertices unless n == 1, where the trivial cycle is `[0]`. For n == 2, no Hamiltonian cycle exists even if the two vertices are connected, because you cannot visit both and return without repeating a vertex. Implement a backtracking search. You may assume the graph is connected if it has at least one edge, but a Hamiltonian cycle may not exist. The function must be deterministic and correct for all valid inputs.
Constraints
1 <= n <= 12
0 <= len(edges) <= n*(n-1)/2
Edges are given as tuples (a, b) with 0 <= a, b < n, a != b. The graph is simple and undirected.
If multiple cycles exist, any valid cycle starting from 0 is acceptable.
Time limit: O(n!) worst-case is acceptable for n <= 12.
Example
>>> hamiltonian_cycle(4, [(0,1),(1,2),(2,3),(3,0),(0,2)])
[0, 1, 2, 3]
>>> hamiltonian_cycle(3, [(0,1),(1,2)])
None
>>> hamiltonian_cycle(5, [(0,1),(0,2),(1,3),(2,4),(3,4),(4,0),(2,3)])
[0, 1, 3, 2, 4]
>>> hamiltonian_cycle(1, [])
[0]
>>> hamiltonian_cycle(2, [(0,1)])
None
45 points
~40 min