Parity and Colouring Arguments

The simplest and most frequently decisive invariant: something mod 2.

Parity facts worth having ready

Fact
Sum of all degrees $=2m$	so the number of odd-degree vertices is even
A permutation’s parity	flips with each transposition; invariant under pairs
A cycle of length $k$	has parity $(-1{)}^{k-1}$
Bipartite ⟺ no odd cycle	the fundamental parity fact for graphs
Sum of $\mathrm{1..}n$	$\frac{n(n+1)}{2}$; its parity has period 4 in $n$
$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is odd	iff $k$‘s bits are a submask of $n$‘s (Kummer/Lucas mod 2)
XOR	is addition mod 2 without carries
A closed walk on a bipartite graph	has even length
$a+b$ and $a-b$	have the same parity

Colouring arguments

Colour the objects so that every move preserves some count. The colouring is the invariant.

Object	Colouring	Consequence
Chessboard	black/white	a domino covers one of each
Chessboard, two opposite corners removed	same	untileable — the counts differ by 2
Grid, knight moves	black/white	a knight always changes colour, so a closed tour needs even length
$3\times n$ grid, trominoes	3-colouring by $(i+j)\mathrm{mod}3$	divisibility constraint
Triangular grid	3-colouring
Infinite board, “spider” moves	weighted by ${\varphi }^{-(x+y)}$	Conway’s soldiers — an unreachable region
Torus / cylinder	wrap the colouring

Conway’s soldiers is the striking one: weighting each cell by ${\varphi }^{-d}$ (with $\varphi$ the golden ratio) makes every jump non-increasing, proving that row 5 is unreachable — an impossibility result no finite search could establish.

Where parity decides the answer

Graph problems

• Eulerian circuit exists iff every degree is even; an Eulerian path iff exactly two are odd.
• Bipartite iff no odd cycle — 2-colour with BFS.
• Chinese postman: the odd-degree vertices (an even number of them) must be paired up and their connecting paths duplicated.
• A graph with all degrees odd has an even number of vertices.

Games

• Many impartial games reduce to “is the number of moves odd or even”.
• Misère Nim’s special case depends on the parity of the number of 1-heaps.
• “Take 1 or 2 stones” games have Grundy value $n\mathrm{mod}3$ — parity generalised.

Permutations

• A permutation is even or odd; transpositions flip it.
• The 15-puzzle’s solvability is a parity condition.
• Sorting by adjacent swaps takes exactly $\mathrm{inv}$ moves, whose parity equals the permutation’s.
• A permutation with $c$ cycles on $n$ elements has parity $(-1{)}^{n-c}$.

Grids and tilings

• Domino tilings need equal colour counts.
• $L$-trominoes on a $2^n\times 2^n$ board with one cell removed: always possible (a classic induction).
• A $k\times n$ board with $1\times k$ pieces: a mod-$k$ colouring decides it.

Handshake-lemma style arguments

${\sum }_v\mathrm{deg}(v)=2|E|$

is a parity statement with wide reach:

• The number of odd-degree vertices is even (used by Christofides and the Chinese postman).
• In any graph, the number of vertices of odd degree in any subgraph is even.
• Sperner’s lemma and the “handshake on a hypergraph” arguments generalise it, and prove existence results like Brouwer’s fixed point theorem combinatorially.

The technique in practice

1. Brute force small cases. Tabulate which are possible.
2. Look at the possible ones mod 2 (then mod 3, mod $k$, then by colouring).
3. If a clean pattern appears, prove the invariant by checking one move.
4. Construct a solution for the permitted cases, usually by induction.

Try mod 2 first, always

It is the cheapest hypothesis and it is correct more often than any other single guess. If mod 2 fails, try mod 3, then a colouring, then a weighted sum.

Beyond parity

When mod 2 is not enough, the same reasoning works with:

• mod $k$ — for $k$-periodic structures;
• a weighted sum $\sum w_i{a}_i$ chosen so every move preserves it;
• XOR — parity in each bit independently, which is exactly what makes Nim work;
• a potential function — a monovariant rather than an invariant.

See also: Invariants and Monovariants · Bipartite Graphs · Proof Techniques