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.
