# Defining a cut-set without referring to partitioning vertices into two groups?

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!

• Your attempt also fails because it claims, for example, that the set of all edges in $K_3$ is a cut-set. – Henning Makholm Oct 27 '12 at 14:26

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.
• I see. Thanks!  – Tim Oct 27 '12 at 15:13