Are subgraphs of a minimum spanning tree, also minimum spanning trees

combinatoricscomputer sciencegraph theory

Clarification: MST = minimum spanning tree

Say I take some complete, weighted graph $G$ – I create a MST of the graph then split $G$ into 2 trees $T_1$ and $T_2$ by removing some edge connecting them called $uv$. My question is, that if I were to take the subgraph of all nodes constuting $T_1$ and $T_2$ and the edges originally connecting them in $G$, would the MSTs of these subgraphs be equivalent to the original MSTs $T_1$ and $T_2$? That is, are the subgraphs of a MST equal to the MSTs of the subgraphs?

Best Answer

I will prove the following Lemma, which answers the question you are asking.

$G$ be a graph with vertex set $V$, and let $T$ be a minimum spanning tree of $V$. Let $T_1$ be any subtree of $T$, and let $W$ be the vertex set of $T_1$. Then $T_1$ is also an MST of $G[W]$, the subgraph of $G$ induced by $W$.

To prove this, let $T_1'$ be any other spanning tree of $G[W]$. Consider the graph $T'$, with vertex set $V$, whose edge set $E(T')$ is given by $$ E(T')=(E(T)\setminus E(T_1))\cup E(T_1') $$

That is, take $T$, remove the edges of $T_1$, then add in the edges of $T_1'$. I claim that $T'$ is a spanning tree of $G$. To see this, note

  • $T'$ is connected. Indeed, for any vertices $v_1,v_2\in V$, there is a path in $T$ connecting them, which can be modified to be a path in $T'$ by replacing the portion of the path that lies in $T_1$ with a corresponding path in $T_1'$.

  • $T'$ has the same number of edges as $T$.

Since $T'$ is a connected graph with $|V|-1$ edges, it is a tree on the same vertex set as $G$, and therefore a spanning tree.

Now, since $T$ was an MST for $G$, we conclude that $w(T')\ge w(T)$. Since $w(T)=w(T_1)+w(T\setminus T_1)$, and $w(T')=w(T_1')+w(T\setminus T_1)$, it follows that $w(T_1')\ge w(T_1)$, thus proving the minimality of $T_1$.

Related Question