= Solution
Assume the finite <graph> is connected, as is necessary for a <spanning tree> to exist. For a disconnected <graph>, the same procedures operate separately on its <connected components of a graph> and produce a minimum spanning <forest>.
Let $T$ be a <minimum spanning tree>. If it omitted the unique lightest <edge> $e$ across the specified <cut of a graph>, adding $e$ would make exactly one <graph cycle>: the <graph path> in $T$ between its endpoints, followed by $e$. Since those endpoints are on opposite sides of the <cut of a graph>, that <graph path> contains another crossing <edge> $f$. Distinct weights give $w_f>w_e$. The <graph> $T+e-f$ is still a <spanning tree>, but has smaller total weight, contradicting minimality. Thus \b[every minimum spanning tree contains $e$], the <minimum spanning tree cut property>.
<Prim algorithm> starts from one <graph vertex>, repeatedly choosing the lightest <edge> from the reached <graph vertices> to an unreached <graph vertex>. Connectivity ensures that such an <edge> exists until all <graph vertices> have been reached. Each choice adds one new <graph vertex> and creates no <graph cycle>. By the <minimum spanning tree cut property>, every chosen <edge> belongs to every <minimum spanning tree>. After $|V|-1$ choices the selected <edges> form a <spanning tree>, necessarily a <minimum spanning tree>.
For <Kruskal algorithm>, suppose the next accepted <edge> $e$ joins two different components of the current <forest>, and let $S$ be one of those components. No previously considered lighter <edge> crosses $S$: an accepted one already joins <graph vertices> within a current component, while a rejected one had its endpoints connected when it was rejected and therefore still has them in a single current component. Consequently $e$ is lightest across the <cut of a graph> defined by $S$. The <minimum spanning tree cut property> again places every accepted <edge> in every <minimum spanning tree>. At termination the accepted <forest> must be connected, since otherwise a crossing <edge> of the original connected <graph> would have been accepted when considered. It is therefore a <minimum spanning tree>.
This reasoning also proves \b[the minimum spanning tree is unique]. Either procedure produces a <spanning tree> all of whose $|V|-1$ <edges> belong to every <minimum spanning tree>; another <minimum spanning tree> cannot have any different <edge>.
For the <minimum spanning tree cycle property>, suppose a <spanning tree> $T$ contained the unique heaviest <edge> $e$ of a <graph cycle> $C$. Removing $e$ splits $T$ into two components. The remainder of $C$ connects the endpoints of $e$, so it contains an <edge> $f$ across these components. This <edge> cannot belong to $T-e$, and $w_f<w_e$. Hence $T-e+f$ is a lighter <spanning tree>. Thus \b[no minimum spanning tree contains $e$].
Finally consider the <reverse-delete algorithm>, processing <edges> from largest to smallest weight. Whenever an <edge> is retained because its deletion would disconnect the current <graph>, it is a <bridge in a graph>; deleting other <edges> later cannot create an alternative path around it, so it remains a <bridge in a graph>. If a currently processed <edge> $e$ is deletable, it lies on a current <graph cycle>. None of that <graph cycle>'s other <edges> can be an earlier retained heavier <edge>, since those are <bridges in a graph>. Thus all other <edges> on the <graph cycle> are lighter than $e$. The <minimum spanning tree cycle property> says that deleting $e$ removes no <edge> of any <minimum spanning tree> of the original <graph>. Throughout, connectivity and the presence of the unique <minimum spanning tree> are preserved. At termination a surviving <graph cycle> is impossible: any of its <edges> was deletable when considered, since that entire surviving <graph cycle> already existed then. The final connected <graph> is a <tree>, and hence is exactly \b[the minimum spanning tree].
Back to article page
