Lesson 7

Let \(G(V,E)\) be an undirected graph, and let \(u,v \in V\) be two of its non-adjacent vertices. If \(\deg(u)+\deg(v) \ge n\), add the edge \(\{u,v\}\) to the graph. Repeat this operation as long as possible. The resulting graph is called the closure of the graph \(G\) and is denoted by \(C(G)\). We will show that the closure is uniquely defined and does not depend on the order of edge additions. Assume that as a result of two different sequences of edge additions, different closures \(G_{1}\) and \(G_{2}\) were obtained. Assume that these graphs first diverged when adding different edges \(\{u_{1},v_{1}\}\) and \(\{u_{2},v_{2}\}\) to the same graph \(H\). Then \[\deg_{H}(u_{1})+\deg_{H}(v_{1}), \deg_{H}(u_{2})+\deg_{H}(v_{2}) \ge n \ .\] Thus, both of these edges will be added in each of the two sequences. Then we can add these two edges simultaneously in \(H\) in both sequences and consider the next difference.

The concept of closure allows expanding the set of edges before proceeding to searching for a Hamiltonian cycle in the graph. This can potentially simplify the search.

Theorem (Chvatal, 1974). An undirected graph \(G\) has a Hamiltonian cycle if and only if it has one in \(C(G)\).

Proof. Let \(\{u,v\} \not \in E\) and \(\deg(u)+\deg(v) \ge n\). We will show that \(G\) is Hamiltonian if and only if \(G+\{u,v\}\) is Hamiltonian. One direction is obvious. Now assume that \(G+\{u,v\}\) is Hamiltonian. If \(G+\{u,v\}\) has a Hamiltonian cycle not passing through the edge \(\{u,v\}\), then it is also in \(G\). If the Hamiltonian cycle in \(G+\{u,v\}\) does pass through the edge \(\{u,v\}\), then \(G\) has a Hamiltonian path with endpoints \(u,v\). Then, by the lemma, \(G\) has a Hamiltonian cycle.◼