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

Graphs with even degrees

Task number: 4172

Prove that any graph with all even degrees does not contain a bridge, i.e. an edge, whose removal will increase the number of components.

  • Solution

    If the edge e belongs to a component C, then after removing e, the other components remain unchanged. The only case where the removal of e could increase the number of components could be in a situation where C would break up into several parts.

    The C component itself induces a connected graph with even degrees, so this component has a closed Eulerian trail. This trail can be selected so that e is its last edge. After removing e, the C will remain an open Eulerian trail, but its existence implies that the C component will not break into two parts, i.e. it will remain connected.

    Therefore, e cannot be a bridge.

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