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