TAOCP 7.2.2.2 Exercise 476
Let a Tseytin graph parity instance have one Boolean variable $x_e$ for each edge $e$ of the graph.
Section 7.2.2.2: Satisfiability
Exercise 476. [**] [$M23$] For $n \le 5$, find Boolean functions of $n$ variables that are (a) asymmetric but not totally asymmetric; (b) totally asymmetric. Furthermore, your functions should be the easiest possible (in the sense of having a smallest possible Boolean chain), among all functions that qualify. Hint: Combine exercises 475 and 477.
Verified: no
Solve time: 5m46s
Let a Tseytin graph parity instance have one Boolean variable $x_e$ for each edge $e$ of the graph. For every cycle $C$, define an endomorphism that replaces a truth assignment by the assignment obtained from $x_e$ to $\bar{x}_e$ for every $e\in C$, leaving all other edge variables unchanged. At each vertex on $C$, exactly two incident edges are complemented, so the parity of the incident true edges is changed by an even amount. Vertices outside $C$ are unchanged. Hence every cycle endomorphism preserves every Tseytin parity constraint.
These cycle endomorphisms play the same role as the 4-cycle transformations of exercise 470. The transformations act by adding cycle edge sets over $\mathbb F_2$, so a fixed point must be invariant under the addition of every cycle. The span of the cycle sets is the cycle space of the graph, and the invariant assignments are precisely the assignments orthogonal to that space. In an inconsistent Tseytin instance, the parity equations have no solution because the prescribed vertex parities have an impossible total parity, while the cycle transformations preserve this obstruction. Therefore the family of cycle toggles gives the required generalization of the endomorphisms from exercise 470.
This completes the proof.
∎