# finding Bondy and Chvatal closure

Given simple graph G(V,E) we have to make it hamiltonian. Bondy and Chvatal theorem states that : Given a graph G with n vertices, the closure cl(G) is uniquely constructed from G by successively adding for all nonadjacent pairs of vertices u and v with degree(v) + degree(u) ≥ n the new edge uv.(from wikipedia)

Now consider tree ( which is also simple graph ) n=6

1<->2
2<->3
3<->4
4<->5
5<->6


And now we realise that we can't get any two verticles(non adjacent) which sums of degrees is ≥ n.

Am i missing something? Seems like quite powerful theorem, but i don't get it.. fully.

Any help will be appreciated.

Chris

-
It would seem that the closure of your tree is itself. Is that a problem? – Gerry Myerson Oct 14 '11 at 21:58
Hmm, but it doesn't make hamiltonian cycle. Am i right? – Spinach Oct 15 '11 at 0:22

## 1 Answer

What the theorem you have in mind says is that: A graph has a hamiltonian circuit (HC) if and only if its "Bondy-Chvatal" closure is Hamiltonian. In the example you cite one cannot add any edges. The graph you start with has no HC and no edges get added so it remains without an HC. What sometimes happens is that one can not easily see if the graph one started with has an HC, but, say after computing the Bondy-Chvatal closure one gets a complete graph. Now the complete graph has an HC so the theorem above tells one that the original graph, where it was not clear if there was an HC or not, has to have an HC.

-
But do you know the method how to make any graph contain HC? I mean in minimum number of additions, because making graph always full is a little pointless. Or am i missing something? – Spinach Oct 15 '11 at 20:03
@Chris I think you are asking about the Hamiltonian completion problem. en.wikipedia.org/wiki/Hamiltonian_completion which is "hard" to solve. – Joseph Malkevitch Oct 16 '11 at 15:52