# At least how many edges of Kn complete graph do we have to remove not to have a Hamilton circuit in the remaining graph?

*print*Print*list*Cite

Expert Answers

changchengliang | Certified Educator

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]

= **(n-1)(n-2)/2**