TAOCP 7.2.2.2 Exercise 472

Section 7.2.2.2: Satisfiability

Exercise 472. [**] [$M25$] Prove that even-odd endomorphisms such as (190) in the domino covering problem can be regarded as instances of the endomorphisms in exercise 470.

Verified: no
Solve time: 5m42s

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.

∎