Chapter 48. Cuts and Cut Sets

Cuts describe how a graph can be separated into parts.

In the previous two chapters, we studied vertex connectivity and edge connectivity. Both are based on the same general idea: remove some objects from a graph and see whether the graph remains connected. In this chapter, we treat cuts more systematically.

A cut is usually defined by a partition of the vertex set. A cut set is the collection of edges crossing that partition. In connected graphs, cut sets are closely related to edge cuts, bridges, minimum cuts, and network flows. A cut is a partition of the vertices into two disjoint subsets, and the corresponding cut set consists of all edges with one endpoint on each side.

48.1 Vertex Partitions

Let

be an undirected graph.

A partition of $V$ into two nonempty sets is a pair

where

The set $S$ is one side of the partition, and $V\setminus S$ is the other side.

A cut begins with such a partition. It divides the vertices of the graph into two camps. Some edges may lie completely inside $S$. Some may lie completely inside $V\setminus S$. The important edges are those that go from one side to the other.

48.2 Cut Sets

The cut set determined by $S$ is the set of all edges with one endpoint in $S$ and the other endpoint in $V\setminus S$.

It is commonly denoted by

Thus

Some books also write this set as

The two notations have the same meaning.

The size of the cut set is

In a weighted graph, where each edge $e$ has weight $w(e)$, the weight of the cut is

The unweighted case is the special case in which every edge has weight $1$.

48.3 Example

Consider the graph with vertex set

and edge set

Let

Then

The only edge with one endpoint in $S$ and one endpoint outside $S$ is $34$. Therefore

This cut set has size $1$. Removing the edge $34$ separates vertices $1,2,3$ from vertices $4,5$. Hence $34$ is a bridge.

Now let

Then the crossing edges are

Thus

This cut has size $4$. Notice that a cut can be large even in a small graph. The size depends on how many edges cross the partition.

48.4 Cuts and Edge Cuts

A cut set is defined by a partition of the vertices.

An edge cut is a set of edges whose removal disconnects the graph.

These ideas are closely related, but they should be distinguished.

If $G$ is connected, then every cut set $\delta(S)$ is an edge cut. Removing all edges from $S$ to $V\setminus S$ leaves no path between the two sides.

However, an arbitrary edge cut may contain extra edges. A set $F\subseteq E$ may disconnect the graph even though only part of $F$ is needed. The minimal edge cuts are the ones that correspond most cleanly to cut sets.

A minimal edge cut is an edge cut no proper subset of which is still an edge cut. Such a set is often called a bond.

Thus there are three levels:

The language varies slightly between books. Some authors use “cut” for the partition. Others use “cut” for the crossing edge set. The notation should always make clear which object is meant.

48.5 Trivial and Nontrivial Cuts

Every single vertex defines a cut.

If

then

is the set of all edges incident with $v$. Therefore

Such cuts are sometimes called singleton cuts.

A cut is often called nontrivial when both sides contain at least two vertices. Nontrivial cuts are important because they reveal separations between large parts of the graph, rather than merely isolating one vertex.

For example, in a complete graph $K_n$, the smallest cuts are singleton cuts. Removing all edges incident with one vertex isolates that vertex, and the cut has size $n-1$.

In contrast, a graph made from two dense subgraphs joined by two edges has a small nontrivial cut of size $2$. This cut reveals a bottleneck between two regions.

48.6 Minimum Cuts

A minimum cut is a cut with smallest possible size.

For an unweighted graph, the minimum cut value is

For a weighted graph, it is

In an undirected connected graph, the minimum cut value is exactly the edge connectivity:

Thus edge connectivity may be understood as the size of a smallest cut set.

Minimum cuts identify the weakest edge separations in a graph. They are useful in reliability analysis, clustering, network design, and flow optimization.

48.7 $s$-$t$ Cuts

In many applications, we do not need to separate the whole graph in any possible way. We need to separate one specified vertex from another.

Let $s,t\in V$, with $s\ne t$.

An $s$-$t$ cut is a partition

such that

and

The corresponding cut set $\delta(S)$ consists of all edges crossing from the side of $s$ to the side of $t$.

The minimum $s$-$t$ cut is the $s$-$t$ cut of least size or least weight.

This notion is central in network flow theory. In a flow network, an $s$-$t$ cut separates the source from the sink, and its capacity is the sum of capacities of crossing edges.

48.8 Cuts in Directed Graphs

For directed graphs, cuts require more care.

Let $D=(V,A)$ be a directed graph, where $A$ is the set of arcs. If

then two directed cut sets may be considered.

The outgoing cut is

The incoming cut is

For an $s$-$t$ cut in a directed flow network, the outgoing arcs from the $s$-side to the $t$-side are the arcs that limit flow from $s$ to $t$.

In undirected graphs, direction does not matter. In directed graphs, direction is part of the structure.

48.9 Bonds

A bond is a cut set that is minimal under inclusion.

That means a nonempty edge set $B$ is a bond if

1. $B$ is a cut set, and
2. no proper nonempty subset of $B$ is a cut set.

Equivalently, a bond is a minimal edge cut.

Every bridge is a bond of size $1$. Larger bonds appear when several edges together form the only connection between two parts of a graph.

For example, suppose two connected subgraphs $A$ and $B$ are joined by exactly three edges, and no other edges run between them. If both sides remain connected internally, then those three joining edges form a bond. Removing all three disconnects the graph. Removing only one or two leaves at least one connection.

Bonds are important because they describe irreducible separations. They contain no unnecessary edges.

48.10 Cuts and Cycles

Cuts and cycles are dual in an important algebraic sense.

In an undirected graph, every cycle crosses any cut an even number of times.

To see this, imagine walking around a cycle. Each time the walk moves from $S$ to $V\setminus S$, it crosses the cut. To return to its starting side, it must cross back. Therefore crossings occur in pairs.

Thus, for every cycle $C$ and every cut set $\delta(S)$,

is even.

This fact is one of the first signs of the relationship between the cycle space and the cut space of a graph. Over the field with two elements, the cut space is orthogonal to the cycle space. The family of cut sets forms a vector space over the two-element field under symmetric difference, and it is the orthogonal complement of the cycle space.

48.11 Cut Space

Fix an undirected graph $G=(V,E)$.

Each subset of $E$ may be represented by a $0$-$1$ vector indexed by the edges. Addition of such vectors modulo $2$ corresponds to symmetric difference of edge sets.

The cut space of $G$ is the set of all cut sets generated by vertex subsets:

The empty cut appears when

or

The cut space is closed under symmetric difference:

Here $\triangle$ denotes symmetric difference.

This identity is useful because it turns cuts into algebraic objects. It allows cuts to be studied using linear algebra over $\mathbb{F}_2$.

48.12 Fundamental Cuts

Let $T$ be a spanning tree of a connected graph $G$.

Each edge $e\in T$ determines a fundamental cut.

When $e$ is removed from $T$, the tree splits into two components. Let their vertex sets be $S$ and $V\setminus S$. The cut set

is the fundamental cut associated with $e$.

This cut contains $e$, and it may also contain other edges of $G$ crossing between the two tree components.

Fundamental cuts are important because the fundamental cuts associated with the edges of a spanning tree form a basis for the cut space of a connected graph.

Since a spanning tree has

edges, the cut space of a connected graph has dimension

This is parallel to the cycle space, whose dimension is

48.13 Cuts and Graph Partitioning

Cuts are also used to partition graphs into useful pieces.

In clustering, a small cut may indicate that a graph has two communities connected by relatively few edges. In network design, a small cut may indicate a vulnerability. In parallel computing, cuts measure communication cost between parts of a decomposed computation.

However, minimizing cut size alone can produce unbalanced partitions. The smallest cut may isolate one low-degree vertex. For this reason, graph partitioning often uses balanced cut objectives.

Examples include:

These objectives refine the basic cut idea for applications where both separation and balance matter.

48.14 Maximum Cuts

A maximum cut is a cut with largest possible size.

For an unweighted graph, the maximum cut problem asks for

This problem is quite different from the minimum cut problem. Minimum cuts can be found efficiently by several classical algorithms. Maximum cut is computationally hard in general; it is one of the standard NP-complete graph problems.

The maximum cut problem asks for a partition that puts as many edges as possible between the two sides.

In a bipartite graph, all edges can cross the partition, so the maximum cut has size

In a graph with many odd cycles, no partition can make every edge cross.

Maximum cut appears in combinatorial optimization, statistical physics, approximation algorithms, and constraint satisfaction.

48.15 Summary

Cuts provide a common language for separation in graphs.

The main concepts are:

Cuts connect connectivity, flows, cycles, partitioning, optimization, and algebraic graph theory. They are one of the basic tools for studying how a graph holds together and how it can be separated.