Cuts And Crossing Edges In Weighted Graphs

Cuts as Vertex Partitions

A cut records how the vertices of a graph are split into two sides. The edges that cross between those sides form the boundary of the split. In a weighted graph, adding the weights of those crossing edges gives the cut’s weight. This is a simple calculation, but it is important to keep the vertex partition separate from the edge set it determines: an edge belongs to the crossing set only when its endpoints lie on opposite sides.

Throughout, graphs are finite, simple and undirected. A weighted graph is a graph $G=(V,E)$ together with a weight function $w:E\to\mathbb{R}$. The weights need not be distinct, and the definition allows negative weights as well as positive ones. For a set $S\subseteq V$, write $V\setminus S$ for its complement in $V$.

Definition: A cut of $G$ is a partition of $V$ into two disjoint sets $A$ and $B$ whose union is $V$. The sets $A$ and $B$ are the sides of the cut; either side may be empty. An edge is a crossing edge if one endpoint is in $A$ and the other is in $B$. The set of crossing edges is denoted $E(A,B)$. The weight of the cut is $$ w(A,B)=\sum_{e\in E(A,B)}w(e). $$

Equivalently, a cut can be described by one subset $S\subseteq V$, with sides $S$ and $V\setminus S$. The crossing-edge set is then $E(S,V\setminus S)$. The cut is nontrivial if both sides are nonempty. If $|V|\ge 1$, choosing $S=\varnothing$ or $S=V$ gives the same trivial cut: its crossing-edge set is empty, so its weight is $0$. If $V=\varnothing$, the only partition also has no crossing edges and weight $0$.

The sides have no preferred order. Thus describing a cut by $S$ or by $V\setminus S$ gives the same partition and the same crossing edges. A cut is a partition of vertices, not a selection of edges. Its edge set is determined by the partition after we check the endpoints of every edge.

Identifying the Crossing Edges

Proposition: For any cut with sides $A$ and $B$, every edge of $G$ is either internal to one side or is a crossing edge, and these possibilities are mutually exclusive. In particular, $$ E=E_G[A]\ \mathbin{\dot\cup}\ E_G[B]\ \mathbin{\dot\cup}\ E(A,B), $$ where $E_G[A]$ is the set of edges with both endpoints in $A$, $E_G[B]$ is the set of edges with both endpoints in $B$, and $\dot\cup$ denotes a disjoint union.

Proof. Let $uv$ be any edge. Since $A$ and $B$ partition $V$, each of $u$ and $v$ lies in exactly one of the two sides. If both endpoints lie in $A$, then $uv\in E_G[A]$. If both lie in $B$, then $uv\in E_G[B]$. Otherwise one endpoint lies in $A$ and the other in $B$, so $uv\in E(A,B)$. These three cases cannot occur together: an endpoint cannot lie in both sides, and an edge whose endpoints are on the same side cannot have one endpoint on each side. Thus every edge belongs to exactly one of the three sets, proving the disjoint-union identity. $\square$

Worked Example: Finding the Crossing Edges

Let $G=(V,E)$ have vertex set $V=\{1,2,3,4,5\}$ and weighted edge set $E=\{12,13,23,24,34,35,45\}$, with $w(12)=2,\ w(13)=5,\ w(23)=1,\ w(24)=4,\ w(34)=3,\ w(35)=6,\ w(45)=2$. Find the crossing edges and weight for the cut with sides $A=\{1,2\}$ and $B=\{3,4,5\}$.

Check each edge by locating its endpoints. Edge $12$ has both endpoints in $A$, so it is internal. Edge $13$ has one endpoint in each side, so it crosses. Edge $23$ crosses for the same reason. Edge $24$ crosses. Edges $34$, $35$, and $45$ have both endpoints in $B$, so they are internal. Therefore $E(A,B)=\{13,23,24\}$.

Substitute the weights of those three edges into the cut-weight definition: $w(A,B)=w(13)+w(23)+w(24)=5+1+4=10$.

Check: The total weight of all edges is $2+5+1+4+3+6+2=23$. The internal edges have weights $2,3,6,2$, which sum to $13$. The crossing and internal weights add to $10+13=23$, agreeing with the total.

A Second Way to Check a Cut Weight

For a vertex $v$, define its weighted degree by $d_w(v)=\sum_{e\text{ incident with }v}w(e)$. This is the sum of the weights of its incident edges. Unlike ordinary degree, it can be negative if some incident edges have negative weight. For a set $S$, let $E_G[S]$ denote the edges with both endpoints in $S$.

Proposition: For any weighted graph with real edge weights and any $S\subseteq V$, $$ w(S,V\setminus S)=\sum_{v\in S}d_w(v)-2\sum_{e\in E_G[S]}w(e). $$

Proof. In the sum $\sum_{v\in S}d_w(v)$, each edge with one endpoint in $S$ and one in $V\setminus S$ contributes its weight exactly once. Each edge with both endpoints in $S$ contributes its weight twice, once to the weighted degree of each endpoint. Edges with neither endpoint in $S$ contribute zero. Therefore this weighted-degree sum is the crossing-edge weight plus twice the weight of the edges internal to $S$. Subtracting that internal contribution gives the stated identity. The argument counts contributions edge by edge and remains valid for empty $S$ and for negative weights. $\square$

Worked Example: Checking a Cut with Weighted Degrees

Let $G=(V,E)$ have $V=\{1,2,3,4\}$, $E=\{12,13,14,23,24,34\}$, and weights $w(12)=7,\ w(13)=2,\ w(14)=5,\ w(23)=4,\ w(24)=1,\ w(34)=6$. Calculate the weight of the cut with $S=\{1,3\}$ and $V\setminus S=\{2,4\}$.

Checking the endpoints gives $12$ as crossing, $13$ as internal to $S$, $14$ as crossing, $23$ as crossing, $24$ as internal to $V\setminus S$, and $34$ as crossing. Hence $E(S,V\setminus S)=\{12,14,23,34\}$, and direct addition gives $w(S,V\setminus S)=7+5+4+6=22$.

Now check the same answer using the weighted-degree identity. The incident edge weights at vertex $1$ sum to $d_w(1)=7+2+5=14$. At vertex $3$, they sum to $d_w(3)=2+4+6=12$. Thus $\sum_{v\in S}d_w(v)=14+12=26$. The only edge internal to $S$ is $13$, with weight $2$, so the identity gives $26-2(2)=26-4=22$. The two calculations agree.

Check: The internal edges on both sides are $13$ and $24$, with total weight $2+1=3$. The total weight of $G$ is $7+2+5+4+1+6=25$, and $22+3=25$, as required.

Complementary Sides and Disconnected Graphs

Proposition: For every $S\subseteq V$, $$ E(S,V\setminus S)=E(V\setminus S,S) \quad\text{and}\quad w(S,V\setminus S)=w(V\setminus S,S). $$

Proof. An edge belongs to $E(S,V\setminus S)$ exactly when one endpoint is in $S$ and its other endpoint is in $V\setminus S$. This condition does not depend on which side is named first, so the two crossing-edge sets are equal. Their weights are sums over the same set of edges and are therefore equal. $\square$

A cut can have no crossing edges even when both sides are nonempty. This happens, for example, when the two sides are unions of different connected components. A graph is connected if every pair of vertices can be joined by a path; in a disconnected graph, there are vertices in different components with no path between them. The cut calculation still uses the same endpoint test: do not infer that an edge crosses merely because the graph has more than one component.

Worked Example: A Cut in a Disconnected Graph

Let $G=(V,E)$ have $V=\{a,b,c,d,e\}$, $E=\{ab,bc,de\}$, and weights $w(ab)=3,\ w(bc)=2,\ w(de)=4$. The graph has one component on $\{a,b,c\}$ and another on $\{d,e\}$.

First take $S=\{a,b,c\}$, so $V\setminus S=\{d,e\}$. Edge $ab$ has both endpoints in $S$, edge $bc$ has both endpoints in $S$, and edge $de$ has both endpoints in $V\setminus S$. No edge crosses, so $E(S,V\setminus S)=\varnothing$. The sum over an empty edge set is $0$, giving cut weight $0$.

For comparison, take $T=\{a,b,d\}$, with complement $\{c,e\}$. Edge $ab$ is internal to $T$. Edge $bc$ crosses because $b\in T$ and $c\notin T$. Edge $de$ crosses because $d\in T$ and $e\notin T$. Thus $E(T,V\setminus T)=\{bc,de\}$, and the cut weight is $2+4=6$.

Check: The total edge weight is $3+2+4=9$. For the first cut, all three edges are internal to one side, so the crossing weight is $0$. For the second, the internal edge $ab$ has weight $3$ and the crossing edges have total weight $6$; $3+6=9$.

Why the Distinction Matters

In a weighted graph, a cut’s weight depends on the weights of its crossing edges, not on how many edges cross. For instance, a cut with two crossing edges of weights $1$ and $2$ has weight $1+2=3$, while a cut with one crossing edge of weight $10$ has weight $10$. The number of crossing edges and the cut weight answer different questions.

Cuts are useful in the study of spanning trees because they express a separation of the vertex set and identify the edges that connect across that separation. For now, the essential task is to describe the partition correctly and compute its crossing-edge set. Any later claim about which crossing edge should be chosen for a spanning tree requires a separate argument; it does not follow from the definition of cut or cut weight alone.

Common Pitfalls

Including an edge whose endpoints are on the same side. In the first worked example, edge $34$ has both endpoints in $\{3,4,5\}$. A wrong calculation might include it and write $5+1+4+3=13$. The correction is to check both endpoints: $34$ is internal, not crossing. The actual crossing set is $\{13,23,24\}$, and its weight is $5+1+4=10$.

Counting a crossing edge twice. When listing $E(A,B)$, each edge is included once, even though it has one endpoint on each side. Summing weighted degrees over one side also counts each crossing edge once; only edges internal to that side are counted twice, which is why the weighted-degree formula subtracts twice their total weight.

Assuming a nontrivial cut must have positive weight. A cut can have no crossing edges, as in the first partition of the disconnected example, so its weight is zero. If edge weights may be negative, a cut weight may also be negative. The definition is a sum, not a positivity condition.

Check Your Understanding

For each question, identify the sides before listing or summing any edges.

Let $V=\{1,2,3,4\}$, $E=\{12,13,23,24,34\}$, and weights $w(12)=3,\ w(13)=5,\ w(23)=2,\ w(24)=4,\ w(34)=1$. Find the crossing-edge set and weight for $S=\{1,4\}$.
Explain why describing a cut by $S$ and by $V\setminus S$ does not change its crossing edges or weight.
For a graph with $V=\{a,b,c\}$, $E=\{ab,bc\}$, and weights $w(ab)=-2,\ w(bc)=5$, calculate the cut weight for $S=\{a,b\}$. Does the definition require nonnegative edge weights?
Prove the weighted-degree identity for $S=\varnothing$ directly, and verify that it gives the same result as the cut definition.
Give a disconnected graph and a nontrivial cut with no crossing edges. Explain why the cut weight is zero.