Edge Cuts in Cubic Graphs
A cut records the edges that join a chosen group of vertices to the rest of a graph. In a cubic graph, each vertex contributes three incidences, so counting those incidences gives strong information about the size of a cut. In particular, the parity of the cut is determined by the parity of the number of vertices on either side. This simple fact also explains why a bridgeless cubic graph cannot have a cut consisting of just one edge.
All graphs in this tutorial are finite and simple. A graph is cubic if every vertex has degree \(3\). For a set \(S\subseteq V(G)\), the induced subgraph \(G[S]\) contains the vertices in \(S\) and all edges of \(G\) whose endpoints both lie in \(S\). Write \(e_G(S)=|E(G[S])|\).
The boundary depends only on the division into \(S\) and its complement: \(\partial_G(S)=\partial_G(V(G)\setminus S)\). This remains true when \(S\) or its complement is empty; in either case the boundary is empty. We will count the edges in the boundary by first counting all degrees of vertices in \(S\).
The Cut-Size Identity and Parity
Proof. Count the incidences of edges with vertices in \(S\). Since every vertex of \(S\) has degree \(3\), there are \(3|S|\) such incidences. Every edge with both endpoints in \(S\) contributes two incidences, giving \(2e_G(S)\) in total. Every edge with exactly one endpoint in \(S\) contributes one incidence, giving \(|\partial_G(S)|\). Edges with neither endpoint in \(S\) contribute none. Therefore \(3|S|=2e_G(S)+|\partial_G(S)|\), which rearranges to the identity. If \(S=\varnothing\), both sides are zero, so the identity includes that case as well. \(\square\)
Proof. By the identity, \(|\partial_G(S)|=3|S|-2e_G(S)\). The term \(2e_G(S)\) is even, and \(3|S|\) has the same parity as \(|S|\), because \(3\) is odd. Subtracting an even number does not change parity, so \(|\partial_G(S)|\) and \(|S|\) have the same parity. This proves both directions: an odd-sized \(S\) has an odd-sized boundary, and an even-sized \(S\) has an even-sized boundary. When \(S\) is empty, both sizes are zero and the statement still holds. \(\square\)
This is a parity statement, not a claim that the boundary is always large. For instance, an odd-sized vertex set must have a nonempty boundary, since zero is even. A stronger lower bound follows when the graph has no bridges, as we will see below.
Worked Example: Cuts in the Complete Graph \(K_4\)
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,13,14,23,24,34\}\). Every vertex has degree \(3\), so \(G\) is cubic. First take \(S=\{1,2,3\}\). Its induced subgraph has edges \(12,13,23\), so \(e_G(S)=3\). The identity gives \(|\partial_G(S)|=3\cdot3-2\cdot3=9-6=3\). Directly, the crossing edges are \(14,24,34\), also three.
Now take \(T=\{1,2\}\). The induced subgraph has one edge, \(12\), so \(e_G(T)=1\). The formula gives \(|\partial_G(T)|=3\cdot2-2\cdot1=6-2=4\). Listing the crossing edges gives \(13,14,23,24\), again four.
Check: the first set has size \(3\), and its boundary has size \(3\), both odd. The second set has size \(2\), and its boundary has size \(4\), both even. The direct edge lists agree with the incidence-count formula.
Bridges and One-Edge Cuts
An edge \(e\) is a bridge if deleting it increases the number of connected components of the graph. A graph is bridgeless if it has no bridges. These definitions apply even when the graph is already disconnected: a bridge is an edge whose deletion separates its own connected component into more components.
Proof. Let \(e\) be the unique edge in \(\partial_G(S)\). In \(G-e\), no edge joins a vertex of \(S\) to a vertex of \(V(G)\setminus S\), because \(e\) was the only such edge in \(G\). The endpoints of \(e\) lie on opposite sides, so after deleting \(e\) there is no path between those endpoints. They were connected by \(e\) before deletion; therefore deleting \(e\) increases the number of components, and \(e\) is a bridge. \(\square\)
Proof. If a cut had size \(1\), the proposition would make its unique edge a bridge, contrary to bridgelessness. Thus a cut in a bridgeless graph cannot have size \(1\). In a cubic graph, the parity theorem says that a cut with \(|S|\) odd has odd size. Its size is a nonnegative odd integer, so it is positive; since it cannot be \(1\), it is at least \(3\). \(\square\)
The condition that the graph be bridgeless matters. Cubic graphs can have one-edge cuts, but their unique crossing edge is then a bridge. The next example constructs one and checks the cut directly.
Worked Example: A Cubic Graph with a Bridge
Take two vertex-disjoint copies of the graph on \(\{a,b,c,d,e\}\) whose edges are all pairs except \(ab,ac,de\). Use primed labels for the second copy, and add the edge \(aa'\). Thus \(V=\{a,b,c,d,e,a',b',c',d',e'\}\), and \(E\) consists of the edges within each copy just specified, together with \(aa'\).
In the first copy, \(a\) is adjacent only to \(d,e\), so its degree within the copy is \(2\). Each of \(b,c,d,e\) has degree \(3\): for example, \(b\) is adjacent to \(c,d,e\), and \(d\) is adjacent to \(a,b,c\). The same degree counts hold in the primed copy. Adding \(aa'\) raises the degree of \(a\) and \(a'\) to \(3\), so the resulting graph is cubic.
Let \(S=\{a,b,c,d,e\}\). There are ten possible pairs among these five vertices, and the three omitted edges are \(ab,ac,de\), so \(e_G(S)=10-3=7\). The identity gives \(|\partial_G(S)|=3\cdot5-2\cdot7=15-14=1\). Indeed, the only edge crossing the cut is \(aa'\). Deleting it separates the two copies, so it is a bridge.
Check: the cut calculation gives \(1\), and the explicit edge list has exactly one crossing edge, \(aa'\). The side \(S\) has five vertices, which is odd, as required by the cut-parity theorem; the other side also has five vertices. This example shows why cubicity alone does not rule out one-edge cuts.
Why the Parity Rule Matters for Matchings
The cut-parity rule also constrains perfect matchings. A matching is a set of edges no two of which share an endpoint; it is perfect if every vertex is incident to exactly one matching edge. The following parity observation does not require the graph to be cubic.
Proof. Count the vertices of \(S\) covered by matching edges. Each matching edge with both endpoints in \(S\) covers two vertices of \(S\). Each matching edge in \(\partial_G(S)\) covers exactly one vertex of \(S\). A matching edge with neither endpoint in \(S\) covers none. Since \(M\) is perfect, all \(|S|\) vertices of \(S\) are covered, so \(|S|=2q+r\), where \(q\) is the number of matching edges internal to \(S\) and \(r=|M\cap\partial_G(S)|\). Hence \(r\) and \(|S|\) have the same parity. The argument also covers \(S=\varnothing\), for which both counts are zero. \(\square\)
Consequently, in a cubic graph, every odd vertex set has an odd number of cut edges, and any perfect matching must use an odd number of those edges. In a bridgeless cubic graph the cut has at least three edges, but the matching parity statement alone does not say that every cut edge belongs to the matching.
Worked Example: A Cut in the Triangular Prism
Let \(G\) have \(V=\{a,b,c,A,B,C\}\) and \(E=\{ab,bc,ca,AB,BC,CA,aA,bB,cC\}\). The lowercase vertices form one triangle, the uppercase vertices form another, and the remaining three edges join corresponding vertices. Each vertex has two neighbors in its triangle and one corresponding neighbor, so every vertex has degree \(3\).
For \(S=\{a,b,c\}\), the induced subgraph has the three edges \(ab,bc,ca\). Therefore \(|\partial_G(S)|=3\cdot3-2\cdot3=9-6=3\). Listing the crossing edges gives \(aA,bB,cC\), a direct count of three.
For \(T=\{a,b,A\}\), the induced edges are \(ab\) and \(aA\), so \(e_G(T)=2\). Thus \(|\partial_G(T)|=3\cdot3-2\cdot2=9-4=5\). Directly, the crossing edges are \(bc,ca,AB,AC,bB\), again five.
Check: both sets have size \(3\), and both computed boundary sizes, \(3\) and \(5\), are odd. The listed crossing edges independently confirm each count. In particular, the boundary of the first set has three edges, not one; the parity rule permits odd sizes but does not force every odd cut to have the same size.
Common Pitfall: Counting Internal Edges Once
A frequent error is to say that a set \(S\) contributes \(3|S|\) boundary edges because each of its vertices has degree \(3\). This counts incidences, not distinct crossing edges: an edge internal to \(S\) is counted at both endpoints, even though it does not belong to the boundary at all. The correction is to subtract two incidences for every internal edge, giving \(|\partial_G(S)|=3|S|-2e_G(S)\).
For example, in the \(K_4\) above, \(S=\{1,2,3\}\) has \(3|S|=3\cdot3=9\) incidences. Its three internal edges contribute \(2e_G(S)=2\cdot3=6\) incidences. Subtracting gives \(9-6=3\) crossing edges, namely \(14,24,34\). The incorrect calculation \(9\) treats all incidences as crossing edges and ignores the internal triangle.
Keep the two conclusions separate: cubicity gives the parity identity, while bridgelessness rules out a boundary of size one. Neither condition should be silently substituted for the other. A cut of odd size may have size \(3\) or more, as the prism example demonstrates; a one-edge cut in a cubic graph is possible, but its edge must be a bridge.
Check Your Understanding
Use the cut identity and the definitions above to answer the following questions.
- In a cubic graph, \(S\) has four vertices and \(e_G(S)=4\). Compute \(|\partial_G(S)|\) and state its parity.
- Prove that if \(|\partial_G(S)|=1\), then both \(S\) and \(V(G)\setminus S\) have odd order.
- Why does the cut-parity theorem alone not prove that every odd cut in a cubic graph has at least three edges?
- In a bridgeless cubic graph, what lower bound does the corollary give for the boundary of any odd-sized vertex set?
- If a perfect matching crosses a set \(S\) of even order, must it use an even or odd number of edges in \(\partial_G(S)\)? Justify using the proposition.