Prove/Disprove: if $v$ is a leaf in all MST's, it has same predecessor

197 Views Asked by At

I've faced a question and failed to disprove it yet, so I am starting to think it is actually a proof.

Prove/disprove: It is given that in all MST's of a an undirected and weighted graph $G$, the vertex $v$ is a leaf. Then, in all such MST's, $v$ has the same predecessor (father).

2

There are 2 best solutions below

0
On BEST ANSWER

False: Take the $3$-cycle on vertices $a,b,c$ with the weight of edges $(a,b)$ and $(a,c)$ equal to two, and the weight of edge $(b,c)$ equal to one. Then $v=a$ is the vertex that is a leaf on all/both MSTs, but it has different predecessors in each.

3
On

Disprove:
Consider Prim's Algorithm:

  1. Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).

  2. Initialize: Vnew = $\{x\}$, where $x$ is an arbitrary node (starting point) from $V$, $E_{new}$ = $\emptyset$.

    Repeat until $V_{new} = V$:

    2.1 Choose an edge $(u, v)$ with minimal weight such that $u$ is in $V_{new}$ and $v$ is not (if there are multiple edges with the same weight, any of them may be picked)

    2.2 Add v to Vnew, and $(u, v)$ to $E_{new}$

  3. Output: $V_{new}$ and $E_{new}$ describe a minimal spanning tree

In step 2.1, we choose the edge which has the minimum weight.

Say that, $T = \{T_1, T_2, ...\}$ is the minimum spanning tree set of $G$.
For a vertex $v$, who is a leaf ın both $T_i$ and $T_j$, $v$ has the same parent in both if and only if all the edges $\forall(u,v) \in E$ have different wieights.