0
$\begingroup$

$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.

$\endgroup$
1
2
$\begingroup$

Preamble

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

                          gr

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

                          m

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.

                          m-a

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.

m-a gr-a

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\}$

                          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]$.

                  gr_t1 and gr_t2

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!

$\endgroup$
1
  • $\begingroup$ please clear comments. $\endgroup$ – Jessica Allen Feb 1 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.