Thursday, May 14, 2026

Uniqueness of edge weight multiset of MST

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: