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 )
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.