TAOCP 7.2.2.2 Exercise 471

Section 7.2.2.2: Satisfiability

Exercise 471. [16] [16] Find all fixed points of the mappings in exercise 470 when the graph is $K_{20}$.

Verified: no
Solve time: 5m40s

Let $M$ be any perfect matching. Apply the transformations successively. If a transformation associated with a 4-cycle $v_0-v_1-v_2-v_3-v_0$ changes $M$, then before the change we have $v_0v_2\in M$ and $v_1v_3\notin M$. The new matching replaces the edge $v_0v_2$ by $v_1v_3$. Since $v_0>v_1$ and $v_0>v_2$, the largest vertex among the four vertices changes from being matched to $v_2$ to being matched to $v_1$. The edge incident with the largest vertex therefore becomes lexicographically smaller under the ordering of perfect matchings induced by the ordered list of vertices.

Choose, among all perfect matchings obtainable from $M$, one that is minimal in this lexicographic ordering. No 4-cycle transformation can change this matching, because any applicable transformation would produce a smaller perfect matching, contradicting minimality. Hence every perfect matching has a descendant fixed by all the 4-cycle endomorphisms.

This completes the proof.

∎