# 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? –  Chris Oct 15 '11 at 0:22