2
$\begingroup$

I wanted to prove Kruskal's algorithm for simple connected undirected graph having pairwise distinct integral edge weights, produces MST using induction on number of nodes. The base case and induction hypothesis are clear.

Base Case: When there are just 2 nodes, since the graph is simple and connected there is just one edge and the prim's algorithm includes that edge and it is the MST.

Induction Hypothesis: Assume that Kruskal's algorithm correctly computes the MST for all connected undirected positive edge weighted simple graphs with $k$ nodes, where $k < n$.

Induction Step: Consider a connected undirected positive edge weighted simple graph $G$ with n nodes. We have to prove that Kruskal's algorithm for this produces a MST.

I'm confused about how to proceed with the proof. I can see that we should do something like removing a vertex so that number of vertices become $<n$ and we can use the induction hypothesis in some way. But on removing we might get many different connected components. Any help on this would be highly appreciated.

$\endgroup$
4
  • $\begingroup$ My guess is that you have to think about which vertex to remove for induction, as if you remove one random $v$, the MST on $G-v$ could look very different from the MST of $G$. Think for instance has $v$ being connected to all the other vertices and containing all the $n-1$ edges of minimal weights... $\endgroup$
    – Qise
    Mar 30, 2023 at 12:38
  • $\begingroup$ @Qise what is the guarentee that such a vertex exist? $\endgroup$ Apr 2, 2023 at 16:07
  • $\begingroup$ @Qise seems to be correct. Adding 1 more vertex, then redoing the Kruskal algortihm from scratch will almost likely result in a different MST (because at every step we have to choose the lowest available weight that does not form a loop). If just 1 weight from the new vertex is lower than all the other weights already present, then the constructed tree will already be different... $\endgroup$
    – James
    Apr 2, 2023 at 16:22
  • $\begingroup$ @Equation_Charmer there's no guarantee it exists. However, chosing $v$ as $argmax_v min_{e\in d(v)} w(e)$ with $d(v)$ representing the edges adjacent to $v$ seems like a good choice. The idea of sorting the vertices in such a way is similar to the idea of sorting the edges in Kruskal. $\endgroup$
    – Qise
    Apr 3, 2023 at 9:23

2 Answers 2

2
$\begingroup$

First, as all weights in graph $G$ are different, the MST is unique. (Proof is everywhere, and notably on Wikipedia's page, I feel it does not add much value to copy it here).

The minimum cost edge $e$ of $G$ is in $G$ MST: take a spanning tree $T$ which does not include $e$. Then add $e$. As it connects two vertices that are already linked in $T$, this creates a cycle. Therefore it is possible to delete another edge of this cycle: this creates a spanning tree which has a lower total cost than $T$. Hence the MST must include $e$.

Now, let's make a graph $G'$ by fusing the two vertices $v_1$ and $v_2$ linked to the minimum cost edge $e$, and modifying the edges in the following way: if a vertex $f$ is connected to both $v_1$ and $v_2$, keep only the edge with the minimum cost. If $G$ MST contains one of these edges, it necessarily contains the one we have kept.

Let's prove that $G$ MST is $G'$ MST plus $e$. We already know that $G$ MST includes $e$, and that all the other edges it includes are in $G'$ with the same weight. Hence when searching all trees in $G$ for the MST, we can reduce the search to the set $S$ of trees which are made of $e$ plus a graph in $G'$, and this graph has to be a tree. So $S$ is in bijection with the set $S'$ of trees in $G'$. The cost of a tree in $S$ is the cost of the corresponding tree in $S'$, plus $e$ cost; hence the minimum trees of $S$ and $S'$ are in correspondence. This proves that $G$ MST is $G'$ MST plus $e$.

$G'$ has $n-1$ vertices, so we can apply the induction hypothesis: $G'$ MST is built with Kruskal algorithm.

The last step is to prove that "classical Kruskal" algorithm on $G$ is equivalent (in terms of chosen edges) to "Kruskal with fusion" algorithm, i.e. selecting the minimum cost edge $e$ in $G$, fusing vertices $v_1$ and $v_2$, then using Kruskal with fusion on $G'$:

  • During classical Kruskal algorithm on $G$, we would never choose an edge that connects vertices that have been fused in Kruskal with fusion: this would create a cycle. (In fact Kruskal algorithm always chooses an edge between two disconnected trees, and in Kruskal with fusion each of those trees is represented by only one vertex).
  • Amongst the other edges, classical Kruskal will choose the minimum cost one. Kruskal with fusion will choose the minimum cost amongst those remaining, but as we have only suppressed edges that have a greater cost than another edge, both algorithms select the same edge.
$\endgroup$
1
  • $\begingroup$ @Equation_Charmer May I ask what is missing from my answer, so that you did not attribute any bounty to it? $\endgroup$ Apr 10, 2023 at 20:48
-1
$\begingroup$

Removing a vertex doesn't seem to be a good idea, if this vertex is not a leaf of a MST. But you don't know whether a vertex may be a leaf of a MST until you prove it.

It is much better to consider the last edge $\{\,x, y\,\}$ you add to the tree. It connects two trees $T_1$ and $T_2$ on $|T_1| < n$ and $|T_2| < n$ vertices ($|T_1| + |T_2| = n$). On one hand these trees are MSTs in the corresponding subgraphs $G(V(T_1))$ and $G(V(T_2))$ of the graph $G$. On the other hand you add the most lightweight edge between them, but this edge is heavier than any edge of $T_1 \cup T_2$.

Suppose that some MST contains some other edge $\{\,u, v\,\}$. If $\{\,u, v\,\} \subseteq V(T_1)$, then $T_1$ was not MST of $G(V(T_1))$ that contradicts the induction hypothesis (and the same for $T_2$). If $u \in V(T_1)$ and $v \in V(T_2)$ (or vice versa) then this edge can be replaced either with $\{\,x, y\,\}$ or with some edge of $T_1$ or $T_2$. In any case such substitution is more lightweight, because $\{\,x, y\,\}$ is the most lightweight edge of all edges between vertices of $T_1$ and $T_2$, but at the same time each edge in $T_1$ and $T_2$ is even more lightweight that $\{\,x, y\,\}$.

P. S. Base case should be the graph $K_1$, otherwise you need to consider this case separately anyway and also make induction step proof a bit longer.

$\endgroup$
3
  • $\begingroup$ @Gonçalo why not? $\endgroup$
    – Smylic
    Apr 6, 2023 at 12:21
  • $\begingroup$ Yeah, I wanted a proof by induction on number of nodes $\endgroup$ Apr 7, 2023 at 10:58
  • $\begingroup$ @Gonçalo Give me please your exact definition of induction by number of vertices. And it should explain why the induction step proof can't be based on removing an edge from the tree (not from the graph BTW) $\endgroup$
    – Smylic
    Apr 7, 2023 at 17:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .