Cut Set

Cut Set: A cut set of a connected graph G is a set S of edges with the following properties

• The removal of all edges in S disconnects G.

• The removal of some (but not all) of edges in S does not disconnects G.

As an example consider the following graph

We can disconnect G by removing the three edges bd, bc, and ce, but we cannot disconnect it by removing just two of these edges. Note that a cut set is a set of edges in which no edge is redundant.