Let $T$ and $T'$ be two spanning trees of a connected graph $G$. For $e \in E(T) - E(T')$, prove that there is an edge $e' \in E(T') - E(T)$ such that $T' + e - e'$ and $T - e + e'$ are both spanning trees of $G$.

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5

Solution

1. Consider an edge $e \in E(T) - E(T')$. Since $e$ is not in $T'$, adding $e$ to $T'$ results in the graph $T' + e$.

• Because $T'$ is a spanning tree, it already spans all vertices of $G$.
• This means there is a path in $T'$ between any two vertices. Adding $e$, which is incident to two vertices already connected by a path in $T'$, must create a cycle in $T' + e$. Let this cycle be $C$.

2. Since $C$ is a cycle in the graph $T' + e$, it contains at least two distinct paths between the vertices incident to $e$.

• These paths consist of edges from $T'$, because $T'$ spans the entire vertex set of $G$.
• As $e \in E(T)$ and $e \not\in E(T')$, the cycle $C$ must contain at least one edge from $T'$ that is not in $T$.
• This edge is denoted by $e' \in E(T') - E(T)$, and it lies on $C$.

3. Now consider the graph $T' + e - e'$.

• By deleting $e'$ from $C$, the cycle is destroyed, and the resulting graph $T' + e - e'$ is acyclic.
• Since $T' + e - e'$ still spans all vertices of $G$, because neither $e$ nor $e'$ disconnects any vertex, it remains connected and contains $n - 1$ edges.
• Therefore, $T' + e - e'$ is a spanning tree of $G$.

4. Next, consider the graph $T - e + e'$.

• Deleting the edge $e$ from $T$ breaks the tree structure and may disconnect the graph, leaving it no longer a tree.
• However, adding the edge $e' \in E(T') - E(T)$ reconnects the graph because $e'$ lies on the cycle $C$, which connects vertices that were possibly disconnected by removing $e$.
• Since the graph $T - e + e'$ now has $n - 1$ edges and remains connected, it must be a tree.
• Additionally, because no cycles were introduced by this operation, $T - e + e'$ is acyclic.
• Thus, $T - e + e'$ is a spanning tree of $G$.