Task list filter?
Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.
Task rankings
Difficulty level
Task tags
Task type
«
«
Two spanning trees
Task number: 4220
Show that for each spanning tree K of the graph G and the edge e∈EG∖EK 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’’ .