Clause-literal consistency graph preserves the Max-3SAT optimum

List the occurrences of $F$ as pairs $(j,r)$ with $1\le j\le m$ and $r\in \{1,2,3\}$, where $(j,r)$ carries the $r$-th listed literal occurrence of clause $C_j$, and let $G$ have vertex set $V=\{(j,r)\}$. Declare two vertices adjacent exactly when either $j=j^{\mathrm{\prime }}$ and $r\mathrm{\ne }{r}^{\mathrm{\prime }}$ (same clause) or $j\mathrm{\ne }{j}^{\mathrm{\prime }}$ and the two carried literals are complementary, that is, one is the negation of the other (distinct clauses). Then $\mathrm{\mid }V\mathrm{\mid }=3m$, no loops or repeated edges occur because adjacency is a symmetric condition on distinct listed pairs, and $G$ is a finite simple graph. Building the vertex list and testing $3m(3m-1)\mathrm{/}2$ pairs runs in polynomial time in the encoding of $F$.

Let an assignment satisfy a set of $t$ clauses. In each satisfied clause choose one of its three occurrences whose literal is true under the assignment. The chosen vertices number $t$, no two lie in the same clause, and no two are complementary, since a single assignment cannot make a variable and its negation both true; hence the chosen set is independent and $\alpha (G)\ge t$. Taking a best assignment gives $\alpha (G)\ge {\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)$.

Conversely let $I$ be an independent set of $G$ of size $k$. By step 1.1, $I$ contains at most one occurrence from each clause, and no two of its occurrences are complementary. Assign a variable $x$ the value true if some occurrence in $I$ carries the literal $x$, the value false if some occurrence in $I$ carries the literal $\mathrm{\neg }x$, and the value false otherwise; this is well defined because complementary occurrences cannot both belong to $I$, and it assigns a value to every variable in polynomial time. Every occurrence in $I$ is then true, so the $k$ distinct clauses containing members of $I$ are all satisfied, and ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)\ge k$. Taking a largest independent set gives ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)\ge \alpha (G)$.

Steps 2.1 and 2.2 give $\alpha (G)\le {\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)$ and $\alpha (G)\ge {\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)$, hence the exact equality $\alpha (G)={\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)$ for every 3-CNF formula with three literal occurrences per clause, including repeated literals and tautological clauses. For $m=0$ the graph is empty and both optima are $0$, so the equality and decoder remain valid. For $m\ge 1$ and $0<\delta \le 1$, with positive scale $m$ by [F4], an instance with ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)=m$ gives $\alpha (G)=m$, and an instance with ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)\le (1-\delta )m$ gives $\alpha (G)\le (1-\delta )m$, so the gap promise transfers with the same $\delta$ and scale $m$. The empty formula is outside this positive-scale gap domain.

The graph of step 1.1 is the complement, on the same occurrence vertices, of the published occurrence graph in [F1]: it joins exactly the pairs that the CLIQUE construction does not. Steps 2.1–3.1 establish directly that this complement graph has independent-set number ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)$ and give a polynomial-time decoder; the cited decision theorem alone states only a satisfiability equivalence.