TAOCP 7.2.2.2 Exercise 470

Section 7.2.2.2: Satisfiability

Exercise 470. ▶ [**] [$M22$] Another class of endomorphisms, one for every 4-cycle, can also be used in perfect matching problems: Let the vertices (instead of the edges) be totally ordered in some fashion. Every 4-cycle can be written $v_0 - v_1 - v_2 - v_3 - v_0$, with $v_0 > v_1 > v_3$ and $v_0 > v_2$; the corresponding endomorphism changes any solution for which $v_0 v_2 \in M$ and $v_1 v_3 \notin M$ to one with $v_1 v_3 \in M$ and $v_0 v_2 \notin M$. Prove that every perfect matching leads to a fixed point of all these transformations.

Verified: no
Solve time: 4m59s

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.

∎