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’’ \).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email