A connected graph $G$ may have multiple MSTs. However, the multiset of MST's edge weight is unique!
=============================================
Proof
Let $T_1$ and $T_2$ be distinct MSTs of $G$. Consider $e_1\in E(T_1)-E(T_2)$. By this, there exists $e_2\in E(T_2)-E(T_1)$ such that both $T_3=T_1+e_2-e_1$ and $T_4=T_2+e_1-e_2$ are spanning trees of $G$. This implies that $w(e_1)=w(e_2)$, and both $T_3$ and $T_4$ are MSTs of $G$. Moreover $T_4$ and $T_2$ have the same edge weight multiset. Now rename $T_4$ as $T_2$, find another edge $e'_1\in E(T_1)-E(T_2)$, and apply the same tool. Eventually we can show that all these MSTs have the same edge weight multiset.
No comments:
Post a Comment