Show a complete graph with n vertices, the weight of a MST is less than or equal to the min weight of cycle that passes through all vertices

Question

I am really struggling with this proof and would really appreciate a detailed explanation:

Show a complete graph with n vertices, the weight of a MST is less than or equal to the min weight of cycle that passes through all vertices (also called a hamiltonian cycle)?

Answer 1

As each vertex is connected to all others, all permutations of nodes can constitute a valid Hamiltonian cycle. Among the possible Hamiltonian cycles of the complete graph, let's pick the one with the least cost.

For an N-node graph, assume that permutation P of the nodes v₁v₂...v_N and set of edges E as defined below constitute the Hamiltonian cycle with the least cost. E={(v₁, v₂), (v₂, v₃), ..., (v_(N-1), v_N), (v_N, v₁)}

Let's prove the questioned lemma by contradiction.

Assume there exists an MST T with the sum of weights greater than the sum of the cost of all edges in E. Let's name that sum of costs as c_E. If that was the case, there would exist another tree T' such that sum of its edge costs is c_E - c_{(vi, v(i+1))}. Basically we could cut the edge between v_N and v₁ and consider the rest of the least-cost Hamiltonian cycle as a tree. As long as the edge (v_N, v₁) had a non-negative cost, c_E - c_{(vi, v(i+1))} would be less than or equal to the cost of T, cost of which was higher than c_E. Therefore, there exists a conflict and our assumption as to the existence of such an MST T must have been incorrect.

Note that the proof above would be valid regardless of which edge you cut, as long as it has a non-negative cost.