1 Answer | Add Yours
For Kn complete graph,
The total number of vertices = n
The total number of edges = n(n-1)/2
By definition, a Hamilton circuit will have each vertex (except for the start vertex) visited only once.
For a Hamilton circuit to exist, the remaining graph would have to be an n-order Cycle graph, Cn, which has exactly n edges.
To avoid having a Cn, there should be n-1 edges left in the remaining graph.
As a result, the least number of edges to be removed from a Kn graph would be:
n(n-1)/2 - (n-1)
= (n-1) [n/2 - 1]
We’ve answered 318,917 questions. We can answer yours, too.Ask a question