Task list filter?
Task rankings
Task tags
«
«
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.