3
$\begingroup$

Let $G$ be a connected weighted undirected graph. Let $T$ be a minimum spanning tree (MST) of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T_a$ and $T_b$, where $Ta$ contains the vertex $a$ and $T_b$ contains the vertex $b$. Now consider the subgraph of $G$, $G_a$, which contains the vertices of $G$ that are in $T_a$, and the edges of $G$ that have both endpoints in $T_a$

Is $T_a$ an MST for the subgraph $G_a$?

Intuitively, I believe $T_a$ is an MST for the subgraph $G_a$, but I'm having a lot of difficulty proving the result.

$\endgroup$

1 Answer 1

2
$\begingroup$

Let’s prove this by contradiction. Say $T_a$ is not an MST of $G_a$, that means there is some cheaper MST $T_a^*$. However, if that were true, then by reconnecting $T_a^*$ to $T_b$ we would obtain a tree that spans $G_a$ that has a lower weight than the MST $T$, which is a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.