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

1 Answer | Add Yours

changchengliang's profile pic

changchengliang | Elementary School Teacher | (Level 2) Adjunct Educator

Posted on

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

 

 

We’ve answered 318,917 questions. We can answer yours, too.

Ask a question