Thursday, May 14, 2026

Beautiful cut and cycle argument

Let $T_1$, $T_2$ be distinct spanning trees of a connected graph $G$. For that for every $e_1 \in E(T_1)-E(T_2)$, there is an edge $e_2 \in E(T_2)-E(T_1)$ such that both $T_2+e_1-e_2$ and $T_1-e_1+e_2$ are spanning trees of $G$.

==============================================

Proof








$T_2+e_1$ has an unique cycle $C$, while $T_1-e_1$ has two components $D_1$ and $D_2$. $C$ crosses the boundary of $D_1$ and $D_2$ at least twice, once at $e_1$. Any other edge of $C$ that crosses that boundary can be $e_2$.

No comments: