Two spanning trees
Task number: 4220
Show that for each spanning tree \( K \) of the graph \( G \) and the edge \( e \in E_G \setminus E_K \) there are two edges of the spanning tree \( e’\) and \( e’’\) such that both \( (K \setminus e’) \cup e \) and \( (K \setminus e’’) \cup e \) are again the spanning trees of the graph \( G \).
Solution
Adding \( e \) to \( K \) yields a cycle of length at least three. For \( e’\) and \( e’’\) we take two edges of this cycle different from \( e \).
Then \( K \setminus e’ \cup e \) is connected because \( K \cup e \) was connected and removing an edge from the cycle does not destroy the connectivity. This graph has no cycles because \( K \cup e \) had a single cycle and we interrupted it by removing \( e’\).
We proceed similarly for \( e’’ \).
