# MST and some facts via an example

$$M$$ is an MST of the Weighted Graph - $$GR$$.

Let $$A$$ be a vertex of $$GR$$ then $$M-$${$$A$$} is also MST of $$GR-$${$$A$$}.

Let $$A$$ be a leaf of $$M$$ then $$M-$${$$A$$} is also MST of $$GR-$${$$A$$}.

If $$e$$ is a edge of $$M$$ then ($$M-$${$$e$$}) is a forest of $$M1$$ and $$M2$$ trees such that for $$M_i, i=1,2$$ is a MST of Induced Graph $$GR$$ on vertexes $$T_i$$.

My notes tell me that the first and last is false. I need some idea of how to understand the validity of these sentences in a more simple and concise manner.

• – D.W. Dec 12 '20 at 18:54

## Preamble

I'll use the following example to illustrate each statement. The graph below will be $$GR$$.

Below is the MST $$M$$ of $$GR$$. These are the bolded edges.

## Statement One

The first statement is false if $$A$$ is an internal vertex of $$M$$. In that case, $$M-\{A\}$$ will result in a forest, which is not an MST.

Suppose we choose $$A = d$$, then $$M-\{A\}$$ will result in the following graph which is not a tree.

## Statement Two

The second statement is true. It is pretty easy to see why $$M-\{A\}$$ in this case is still an MST.

Suppose we choose $$A = a$$ (our only choices are $$\{a,g,i\}$$), then $$M-\{A\}$$ (left) will result in the following tree. We can compare it to $$GR-\{A\}$$ (right) and see that it is an MST.

## Statement Three

The third statement is true.

Formal Proof of Statement Three

Proof: Let $$GR[T_1]$$ and $$GR[T_2]$$ be induced subgraphs of $$GR$$ and $$M_1'$$ and $$M_2'$$ are their MSTs respectfully. Let $$X$$ be the set of edges that connect vertices of $$T_1$$ and $$T_2$$ in $$GR$$ (note $$e \in X$$).

To show $$M_1$$ and $$M_2$$ are MSTs, we must show is $$M_1 = M_1'$$ and $$M_2 = M_2'$$.

Let $$w(M) = w(M_1) + w(e) + w(M_2)$$ be the cost of the MST of $$GR$$.

Let $$w(M_1')$$ and $$w(M_2')$$ be the cost of the MST of $$GR[T_1]$$ and $$GR[T_2]$$.

Construct the graph $$M' = M_1' \cup e \cup M_2'$$. This graph is the MSTs of both induced graphs and a single edge that connects them. Note, we could use any edge from $$X$$, however for it to be a MST, we must select the minimum cost edge of $$X$$. So $$w(M') = w(M_1') + w(e) + w(M_2')$$.

Since $$w(M_1')$$, $$w(e)$$, and $$w(M_2')$$ are minimal, then $$w(M')$$ is minimal. Since $$w(M')$$ is minimal, then $$w(M') = w(M)$$. So,

\begin{align} w(M_1') + w(e) + w(M_2') &= w(M') \\ &= w(M) \\ &= w(M_1) + w(e) + w(M_2). \end{align}

So $$w(M_1') = w(M_1)$$ and $$w(M_2') = w(M_2)$$, thus $$M_1' = M_1$$ and $$M_2' = M_2$$. Hence, $$M_1$$ and $$M_2$$ are MSTs.

Intuition of Proof

I'll pick $$e = \{c,d\}$$ to be the edge with weight one for this example. Below is $$M-\{e\}$$

Let $$M_1$$ be the tree on the left and $$M_2$$ be the tree on the right. Then $$T_1 = \{a,b,c\}$$ is the vertex set of $$M_1$$ and $$T_2 = \{d,e,f,g,h,i\}$$ is the vertex set of $$M_2$$. We need to construct the induced subgraphs of $$GR$$ on $$T_1$$ and $$T_2$$, $$GR[T_1]$$ and $$GR[T_2]$$. Below on the left is $$GR[T_1]$$, and below on the right is $$GR[T_2]$$.

Now you can see the $$M_1$$ is the MST of $$GR[T_1]$$ (similarly for $$M_2$$).

In the proof, we abuse the fact that the MST of the induced subgraph and the original graph are minimal. We also use the fact that $$M$$ must contain $$e$$, the smallest edge that connects $$M_1$$ and $$M_2$$. We can conclude the only MST of the induced graphs is $$M_1$$ (for the left) and $$M_2$$ (for the right).

I hope this helps!

• please clear comments. – Jessica Allen Feb 1 at 12:25