﻿ 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

# 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

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

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 v1v2...vN and set of edges E as defined below constitute the Hamiltonian cycle with the least cost. E={(v1, v2), (v2, v3), ..., (v(N-1), vN), (vN, v1)}

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 cE. If that was the case, there would exist another tree T' such that sum of its edge costs is cE - c(vi, v(i+1)). Basically we could cut the edge between vN and v1 and consider the rest of the least-cost Hamiltonian cycle as a tree. As long as the edge (vN, v1) had a non-negative cost, cE - c(vi, v(i+1)) would be less than or equal to the cost of T, cost of which was higher than cE. 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.

Suppose the weight of the minimum spanning tree is greater than a Hamiltonian Cycle, choose any edge in the cycle and remove it, it will become a new spanning tree (covers all the vertices) that has a less weight than the minimum spanning tree, hence the contradiction.