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