Parity Arguments in Graph Proofs

Parity as a Counting Tool

In a graph proof, exact counts can sometimes be harder to determine than whether a count is even or odd. Reducing a count modulo two often reveals a contradiction with little additional information. The key is to count incidences carefully: an edge with both endpoints in a selected vertex set contributes twice to the degree sum of that set, while an edge crossing from the set to its complement contributes once.

All graphs in this tutorial are finite and simple. For a vertex \(v\), its degree \(\deg(v)\) is the number of edges incident with \(v\). For a vertex set \(S\subseteq V(G)\), let \(E(G[S])\) be the edges with both endpoints in \(S\), and let \(\partial(S)\) be the set of edges with exactly one endpoint in \(S\). The edges of \(\partial(S)\) are the edges crossing the cut determined by \(S\) and \(V(G)\setminus S\). We use “even” and “odd” in their usual integer sense; an equality modulo two records only whether two integers have the same parity.

This identity is an incidence count. An edge internal to \(S\) contributes one to the degree of each of its two endpoints, so it contributes two to the sum. An edge crossing the cut has just one endpoint in \(S\), so it contributes one. An edge with both endpoints outside \(S\) contributes zero. These cases exhaust the edges. In particular, the formula remains valid for the empty set and the whole vertex set: both sides are zero when \(S=\varnothing\), and \(\partial(V(G))=\varnothing\) when \(S=V(G)\).

The Even-Odd-Degree Rule

Proof. Take \(S=V(G)\) in the identity. There are no edges crossing from \(V(G)\) to its complement, so \(\sum_{v\in V(G)}\deg(v)=2|E(G)|\), which is even. The sum of a finite list of integers is odd precisely when the list contains an odd number of odd entries: even entries do not affect parity, and adding an odd number of odd entries gives an odd sum. Since the degree sum is even, the number of odd-degree vertices must be even. If \(V(G)=\varnothing\), there are no odd-degree vertices, and their number, zero, is even as required. \(\square\)

This is a parity form of the handshake count. It constrains the number of odd degrees, not the particular values of the degrees. The same argument applies separately to each connected component: apply the theorem to the graph formed by that component’s vertices and edges. Thus each component has an even number of odd-degree vertices, even when the whole graph has several components or isolated vertices.

Degree Sums on a Selected Set

The identity for a set \(S\) is useful even when the degrees outside \(S\) are irrelevant. Modulo two, the term \(2|E(G[S])|\) disappears, leaving \(\sum_{v\in S}\deg(v)\equiv|\partial(S)|\pmod 2\). So an odd degree sum on \(S\) forces an odd number of crossing edges, and an even degree sum forces an even number. This can test a proposed cut without requiring the exact number of edges internal to \(S\).

Proof. In the sum \(\sum_{v\in S}\deg(v)\), each even degree contributes zero modulo two and each odd degree contributes one. Therefore the sum has the same parity as the number of odd-degree vertices in \(S\). By the key identity, the sum also has the same parity as \(|\partial(S)|\), because \(2|E(G[S])|\) is even. The two quantities therefore have the same parity. If all degrees in \(S\) are even, the number of odd-degree vertices in \(S\) is zero, so \(|\partial(S)|\) is even. The argument includes \(S=\varnothing\), for which both counts are zero. \(\square\)

Why a Cycle Crosses a Cut Evenly

A second useful parity argument follows an object edge by edge rather than adding degrees. As a cycle is traversed, every crossing edge switches whether the current vertex lies in \(S\) or outside \(S\). To return to the starting vertex, the number of switches must be even. This argument does not depend on how many other edges the graph has.

Proof. Write the cycle in order as \(v_0v_1\cdots v_{\ell-1}v_0\), where \(\ell\ge3\) and the listed vertices are distinct. For each index \(i\), with indices taken cyclically, the edge \(v_iv_{i+1}\) crosses the cut exactly when one endpoint is in \(S\) and the other is outside \(S\). Record membership as \(1\) for a vertex in \(S\) and \(0\) for a vertex outside \(S\). A crossing edge changes this value, while a noncrossing edge leaves it unchanged. After traversing all \(\ell\) edges, the membership value returns to its starting value at \(v_0\). A sequence of changes by \(0\) or \(1\) that returns to its initial value must contain an even number of changes, since each change toggles between \(0\) and \(1\). Hence the cycle uses an even number of edges of \(\partial(S)\). \(\square\)

Using Parity Carefully

Parity arguments are most effective when the count is stated precisely. A claim that “the edges contribute an even amount” is not enough: specify which edges are being counted and whether an internal edge contributes twice or a crossing edge contributes once. The set identity makes those contributions explicit, and the cycle argument tracks membership changes in their order.

A common error is to equate the degree sum over \(S\) with the number of crossing edges, omitting the internal edges’ contributions. In the cut example, that incorrect calculation would say the degree sum \(5\) equals the crossing count \(3\). The numbers are not equal: the one internal edge contributes twice, so the correct calculation is \(5=2\cdot1+3\). The two quantities have the same parity, which is the conclusion the modulo-two argument permits.

Parity usually provides a necessary condition, not a complete description. For instance, an even number of odd entries in a proposed degree list passes the even-odd-degree test, but that alone does not construct a graph with those degrees. Likewise, knowing a cut has even size does not determine its exact size. Use parity to rule out a configuration when it violates a necessary condition; use a separate argument when the goal is to prove existence or determine an exact count.