1
$\begingroup$

From Wikipedia:

a cut is a partition of the vertices of a graph into two disjoint subsets.

The cut-set of the cut is the set of edges whose end points are in different subsets of the partition.

I would like to see if a cut-set can be defined without referring to partitioning the vertices into two groups?

I have tried this one " a cut-set is a subset of edges such that removing them will increase the connected components of the graph". But later realize that a cut-set can have no edges, if there are no edges between the two groups of vertices in the original graph.

Thanks!

  • 1
    Your attempt also fails because it claims, for example, that the set of all edges in $K_3$ is a cut-set.2012-10-27

1 Answers 1

3

In an undirected graph, a set $A$ of edges is a cut-set iff one can choose a direction for all edges in $A$ such that there is no path outside $A$ that connects the front vertex of an edge in $A$ to the back vertex of a (possibly different) edge in $A$.

We can then reconstruct a possible partitioning leading to this set by letting one partition be all the union of all connected components of $G\setminus A$ that contain the front vertex of at least one edge in $A$, and the other partition contain all other vertices.

If you don't want to consider partitions where one of the subsets is empty, you'll have to add a codition that the empty set of edges is only a cut-set if the original graph is not connected.

  • 0
    I see. Thanks! $ $2012-10-27