Let G be a connected multigraph A edgecut of G is a set F of

Let G be a connected multigraph. A edge-cut of G is a set F of edges whose removal disconnects G. A edge-cut F is minimal, provided that no subset of F other than F itself is a edge-cut. Prove that a bridgeis always a minimal edge-cut, and conclude that the only minimal edge-cuts of a tree are the sets consisting of a single edge

Solution

By definition , a bridge B is an edge whose removal increases the number of connected components of the graph G.

Being a single edge, B is definitely a minimal edge-cut (as G is given to be connected). [ removal of B creates at least one more connected component].

Equivalently, an edge is a bridge if it is not contained in any cycle.

As a tree has no cycle, the minimal edge-cuts are the sets containing single edges. (Otherwise an edge may be removed without removing the connectivity)