Homework 8

Due Wednesday, February 19 at 5:00 PM. Please refer to the homework policy here.

Some useful definitions and facts

Let $G = (V,E)$ be an undirected graph.

• An edge set $F \subseteq E$ spans an edge $e = \{u,v\} \in E$ if $u$ and $v$ are connected in $F$.
• An edge set $F \subseteq E$ is spanning if it spans every edge.
• An edge set $F \subseteq E$ is acyclic and is a forest if it does not contain any cycles. In particular, between any pair of vertices connected by $F$, there is a unique path between them in $F$.
• Let $G$ be connected. An edge set $F \subseteq E$ is a spanning tree if it is both spanning and a forest.
• Combining the definition of spanning and forest, an edge set $F \subseteq E$ is a iff every pair of vertices is connected by a unique path in $F$.

Problems

1. Let $T_1$ and $T_2$ be two spanning trees, and let $e \in T_1 \setminus T_2$ be an edge in $T_1$ but not $T_2$. Prove that there exists an edge $d \in T_2 \setminus T_1$ such that $T_2 - d + e$ and $T_1 - e + d$ are both spanning trees. (Here "$+$" denotes adding an edge and "$-$" denotes deleting an edge.) (Such a pair $e$ and $d$ are sometimes called a mutually exchangeable pair.)
2. Let $T_1$ and $T_2$ be two spanning trees. Show that there exists a one-to-one mapping $\varphi: (T_2 \setminus T_1) \to (T_1 \setminus T_2)$ such that for every $e \in T_2$, the tree $T_1 - \varphi(e) + e$ is a spanning tree. ¹
3. Let $T$ be a spanning tree in a weighted graph. Prove that $T$ is the minimum weight spanning tree iff $w(T) \leq w(T')$ for every spanning tree $T'$ with $|{T \setminus T'}| = 1$ (that is, for every spanning tree $T'$ differing in exactly one edge.) ²