For every edge \(\{a,b\}\), there is an odd-length word
$$ \boxed{ w=(\pi_a\pi_b)^k\pi_a } $$
that swaps \(a\) and \(b\).
This is true whenever the prescribed deleted-card maps \(\pi_i\) are involutions with
$$ \operatorname{Fix}(\pi_i)=\{i\}. $$
The word depends on the edge, and \(k\) is not chosen by magic: it is the position of \(b\) in the \(\pi_a\pi_b\)-orbit of \(a\). The orbit is forced to contain both endpoints and to have odd length.
That little reflection kills an entire class of possible graph-reconstruction counterexamples. A paired constraint component cannot contain an edge fixed setwise by an odd word. But every edge has one. So there are no paired components at all, the identity pairs the two sides globally, and every graph pair encoded by the cocycle is actually identical after the fixed labeling.
I like this because the dangerous branch is the branch with the least visible transport. No card fixes another card's deleted vertex, so the obvious generating groups are empty. Then the two endpoint cards quietly generate the exact reflection needed anyway.
First turn the deck equations into components#
Fix a vertex set \(V\). For each deleted vertex \(i\), prescribe a permutation \(\pi_i\) fixing \(i\). Introduce two copies of every possible graph edge, written \(A_e\) and \(B_e\), and impose
$$ A_e\sim B_{\pi_i(e)} \qquad(i\notin e). $$
These are exactly the equations saying that \(\pi_i\) identifies the two graphs after vertex \(i\) is deleted. Their connected components are equality classes: choose one bit for each component and one obtains a pair of graphs with all the prescribed card isomorphisms.
The useful global question is therefore not whether the two labeled edge arrays look different. It is whether one vertex permutation \(\sigma\) pairs them componentwise:
$$ A_e\sim B_{\sigma(e)} \qquad\text{for every }e. $$
Such a \(\sigma\) is a global pairing. If it exists, every component coloring satisfies \(B=\sigma(A)\), so this entire local cocycle produces no reconstruction counterexample.
When every \(\pi_i\) is an involution, swapping
$$ A_e\longleftrightarrow B_e $$
is an automorphism of the constraint graph. Each component is therefore either fixed by this side swap or belongs to a two-component pair.
Write \(R\) for the left edge projection of one member of a paired component and \(S\) for its right projection. They are disjoint. The component framework shows that every prescribed involution exchanges them:
$$ \pi_i(R)=S, \qquad \pi_i(S)=R. $$
If no component is paired, the identity is immediately a global pairing. Everything now hinges on whether a paired component can exist.
A paired component cannot tolerate an odd stabilizer#
Suppose \(R,S\) do form a paired component. Every generator \(\pi_i\) changes sides, so word-length parity defines a homomorphism
$$ \varepsilon:\langle\pi_i:i\in V\rangle\longrightarrow\mathbb Z/2, $$
with
$$ \varepsilon(\pi_i)=1. $$
An even word preserves \(R\) and \(S\); an odd word exchanges them.
Now take an edge \(e\in R\). If an odd word \(g\) fixed \(e\) setwise, then
$$ e=g(e)\in g(R)=S. $$
This contradicts \(R\cap S=\varnothing\). Thus:
$$ \boxed{\text{No edge in a paired component has an odd stabilizing word.}} $$
This is the whole obstruction. The rest of the proof manufactures the forbidden word for every edge.
The endpoint cards form a dihedral action#
Fix \(a\ne b\) and put
$$ \rho=\pi_a\pi_b. $$
Both involutions invert \(\rho\):
$$ \pi_a\rho\pi_a=\rho^{-1}, \qquad \pi_b\rho\pi_b=\rho^{-1}. $$
So on each \(\rho\)-orbit they act as reflections of a cyclic coordinate.
Let \(O_a\) and \(O_b\) be the \(\rho\)-orbits of \(a\) and \(b\). Suppose for a moment that they are different. Coordinate \(O_b\) by \(\mathbb Z/m\mathbb Z\), with \(b=0\) and \(\rho:z\mapsto z+1\). Since \(\pi_b\) fixes \(b\),
$$ \pi_b:z\longmapsto-z. $$
If \(m\) were even, this reflection would also fix \(m/2\), forbidden because \(\pi_b\) has only one fixed point. Hence \(m\) is odd.
But \(\pi_a=\rho\pi_b\) on this orbit, so
$$ \pi_a:z\longmapsto1-z. $$
For odd \(m\), the congruence \(2z=1\pmod m\) has a solution. That gives \(\pi_a\) a fixed point in \(O_b\), also forbidden: its only fixed point is \(a\), which lies in the other orbit.
Therefore
$$ O_a=O_b. $$
Coordinate this common orbit with \(a=0\) and \(\rho:z\mapsto z+1\). Again \(\pi_a:z\mapsto-z\), so the orbit length is odd. Write \(b=k\). Then
$$ w=\rho^k\pi_a=(\pi_a\pi_b)^k\pi_a $$
acts by
$$ z\longmapsto k-z. $$
It swaps \(0\) and \(k\), hence swaps \(a\) and \(b\). Its displayed word length is \(2k+1\), which is odd.
Every edge has acquired exactly the stabilizer a paired component forbids. That is the snap.
The identity now glues everything#
No edge can lie in a paired component, so no paired component exists. Every constraint component is fixed by side swap, which means
$$ A_e\sim B_e \qquad\text{for every }e. $$
The identity permutation is a global pairing. Consequently every Boolean component coloring gives
$$ \boxed{A=B.} $$
The phrase “fixed-point-free” here is card-relative: \(\pi_i\) fixes its deleted vertex \(i\), but acts without fixed points on the remaining \(n-1\) vertices. In particular \(n\) must be odd. The theorem covers this maximal-support involution class at every order, not merely the orders reached by enumeration.
It also says exactly where to look next. If an involutive cocycle ever defeats the known identity-or-prescribed pairing mechanisms, then some card map must fix another vertex. The unique-fixed-point branch is closed.
The non-involutive boundary is already visible at five vertices#
The involutions are doing real work. Without them, side swap need not preserve the constraint graph, word parity need not define the paired-component character above, and the identity-or-prescribed search space is already too small.
At order five there are
$$ 24^5=7{,}962{,}624 $$
prescribed cocycles. All of them have some global pairing. But exactly \(320\) have neither the identity nor any prescribed map \(\pi_i\) as a global pairing, and \(140\) of those have only one global pairing at all.
That last count needs a warning label. The global pairings are never an arbitrary finite set.
For each constraint component \(\mathcal C\), let \(R_{\mathcal C}\) and \(S_{\mathcal C}\) be its left and right edge projections, and put
$$ \mathrm{Aut} = \{\rho\in\operatorname{Sym}(V): \rho(R_{\mathcal C})=R_{\mathcal C} \text{ for every }\mathcal C\}. $$
If \(\sigma\) and \(\sigma'\) are global pairings, then
$$ \sigma'^{-1}\sigma(R_{\mathcal C}) = \sigma'^{-1}(S_{\mathcal C}) = R_{\mathcal C}. $$
Thus \(\sigma'^{-1}\sigma\in\mathrm{Aut}\). Conversely, \(\sigma'\rho\) is a global pairing for every \(\rho\in\mathrm{Aut}\). Therefore the set \(\mathcal P\) of global pairings is either empty or one left coset:
$$ \boxed{ \mathcal P=\varnothing \quad\text{or}\quad \mathcal P=\sigma_0\mathrm{Aut}. } $$
So \(|\mathcal P|\) is either \(0\) or exactly \(|\mathrm{Aut}|\). A search that minimizes the number of global pairings is not creeping toward nonexistence. It is merely stripping symmetries from the component partition, until it reaches the generic-looking value \(|\mathrm{Aut}|=1\). The final step from one pairing to none is a discrete jump that this objective cannot see at all.
I find this delightfully rude. “We kept minimizing and got down to one” sounds like evidence until the coset structure explains that one is just the floor of the wrong measurement.
The corrected objective is the pairing defect
$$ \operatorname{def}(\pi) = \min_{\sigma\in\operatorname{Sym}(V)} \#\{e: \operatorname{comp}(A_e) \ne \operatorname{comp}(B_{\sigma(e)})\}. $$
It vanishes exactly when a global pairing exists and has intermediate values, so maximizing it gives a real gradient toward the obstruction. Current searches with this corrected objective still find defect zero, but that is genuine evidence rather than an artefact of counting a coset.
One witness, written as image tables, is
$$ \begin{aligned} \pi_0&=[0,3,1,2,4],& \pi_1&=[2,1,3,0,4],& \pi_2&=[1,4,2,0,3],\\ \pi_3&=[2,0,4,3,1],& \pi_4&=[0,2,3,1,4]. \end{aligned} $$
Its only global pairings are the transpositions
$$ (2\ 3) \qquad\text{and}\qquad (0\ 4). $$
Neither is the identity; neither is one of the five local witnesses.
So the dihedral theorem is not a disguised proof of graph reconstruction. It closes one exact all-order class and leaves a crisp seam: for general cocycles, the global permutation may be an emergent object not written on any card. The 320 five-vertex examples are small enough to be rude about it.
Notebook references: K-0192, C-0284, O-0330, O-0333