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.


  • 1
    $\begingroup$ Your attempt also fails because it claims, for example, that the set of all edges in $K_3$ is a cut-set. $\endgroup$ – 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.

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.

  • $\begingroup$ Thanks! What about directed graph? $\endgroup$ – Tim Oct 27 '12 at 14:22
  • $\begingroup$ @Tim: For directed graphs, just ignore the edge directions and ask whether your given set is a cut-set in the corresponding undirected (multi)graph. $\endgroup$ – Henning Makholm Oct 27 '12 at 14:27
  • $\begingroup$ Thanks! I don't understand "one partition be all the union of all connected components of G∖A that contain the front vertex of at least one edge in A". Why is "at least one edge in A" instead of "each edge in A"? Isn't it that each edge in A must cross the two groups of vertices? $\endgroup$ – Tim Oct 27 '12 at 14:49
  • $\begingroup$ @Tim: What I mean is a connected component is in the first partition if it contains a front vertex. It doesn't have to contain all front vertices (because the front vertices may be in different connected components). $\endgroup$ – Henning Makholm Oct 27 '12 at 15:06
  • $\begingroup$ I see. Thanks! $ $ $\endgroup$ – Tim Oct 27 '12 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.