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
    Thanks! What about directed graph?2012-10-27
  • 0
    @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.2012-10-27
  • 0
    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?2012-10-27
  • 0
    @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).2012-10-27
  • 0
    I see. Thanks! $ $2012-10-27