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 eEGEK 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