2
$\begingroup$

I'm pracitcing exams towards finals,

Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$.

Prove : for every 2 distinct MST $T,T'$ there is a sequence of $k$ MST's such that every 2 MST's $T_i,T_i+1$(+1 on the index) in the list are neighbours and at the end of the sequence we get $T$

$T' = T_1,T_2,T_3,\ldots,T_k=T$

hope to get help.

$\endgroup$
1
$\begingroup$

This is a generalization of the Uniqueness property of minimum spanning trees, and the proof is almost the same:

  1. Note there is at least one edge that belongs to exactly one of $T$ and $T'$. Among such edges, let $e_1$ be the one with least weight. Without loss of generality, assume $e_1 \in T$.

  2. As $T'$ is an MST, $e_1\cup T'$ must contain a cycle $C$ with $e_1$.

  3. As a tree, $T$ contains no cycles, therefore $C$ must have an edge $e_2\notin T$.

  4. Since $e_1$ was chosen as the lowest-weight edge among those belonging to exactly one of $T$ and $T'$, the weight of $e_2$ must be no less than the weight of $e_1$.

  5. As $e_1$ and $e_2$ are part of the cycle $C$, replacing $e_2$ with $e_1$ in $T'$ therefore yields a spanning tree $T''$ with no larger weight, thus also a minimum spanning tree. Since $e_1\in T$ and $e_2\notin T$, $T''$ is more "closer" to $T$ than $T'$.

  6. Repeat the processes above for $T$ and $T''$. Finally you will get a sequence of mimimum spanning trees between $T$ and $T'$.

| cite | improve this answer | |
$\endgroup$

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