\documentclass[11pt]{amsart} \IfFileExists{lmodern.sty}{\usepackage[T1]{fontenc}\usepackage{lmodern}}{} \usepackage{amsmath,amssymb,amsthm} \usepackage[hidelinks]{hyperref} \setlength{\emergencystretch}{1.5em} \IfFileExists{geometry.sty}{\usepackage[letterpaper,left=0.75in,right=0.75in,top=0.7in,bottom=0.8in]{geometry}}{\setlength{\textwidth}{7in}\setlength{\textheight}{9.4in}\setlength{\oddsidemargin}{-0.25in}\setlength{\evensidemargin}{-0.25in}\setlength{\topmargin}{-0.5in}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \title[An $83/84$ approximation for a cubic three-occurrence Horn class]{An $83/84$ approximation for a cubic three-occurrence Horn class} \author{Frank Vega} \address{Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA} \email{vega.frank@gmail.com} \date{November 21, 2026} \subjclass[2020]{68Q25, 68W25, 68Q15, 68Q17, 05C69} \keywords{approximate-computing, max-sat, independent-set-problem, lean4, np-hard, satisfiability, unique-games-conjecture} \begin{document} \begin{abstract} We study an unweighted MAX-HORN-2SAT class, which is also a class of MAX 2-SAT instances, in which every Boolean variable has exactly three literal occurrences. For a simple cubic graph $H=(V,E)$ the formula $T_H$ satisfies \[ \operatorname{OPT}(T_H)=4|V|+|E|+\alpha(H), \] and every assignment of value $A$ is repaired in polynomial time to an independent set of size at least $A-(4|V|+|E|)$. This gives a polynomial-time $83/84$ approximation from a cubic independent-set approximation and a near-bipartite cut algorithm, an $L$-reduction from cubic MIS, and APX-completeness. For simple $d$-regular graphs the optimum is $(d+1)|V|+|E|+\alpha(H)$ and the factors are: $(3d+2)/(3d+3)$ from the all-true assignment, which is at least $83/84$ for $d\ge27$; $83/84$ from the Berman--Fujito guarantee for $d\ge22$ and, with a semidefinite cut rounding, for $d=21$; and $(21d+20)/(21d+21)$ from any $6/7$-approximate independent set. For arbitrary simple graphs the optimum is $n+3m+\alpha(H)$. MAX-CUT on a $d$-regular graph $G$ reduces to MAX 2-SAT with the clauses $(x_u\vee x_v)$ and $(\neg x_u\vee\neg x_v)$ per edge, of value $m+\operatorname{cut}(S)$. The conflict graph $H(G)$ is $(d+1)$-regular and $\alpha(H(G))=m+\operatorname{maxcut}(G)$. A Goemans--Williamson cut gives on $T_{H(G)}$ the factor $1-\frac{1-\alpha_\varepsilon}{6d+12}\ge83/84$ for every $d\ge1$, and a $\gamma$-dependent analysis gives $1-\frac{0.1053}{6d+11.5}$, where $\alpha_\varepsilon=\alpha_{\mathrm{GW}}-10^{-5}$ and $\gamma=\operatorname{maxcut}(G)/m$. For arbitrary simple graphs without isolated vertices the factor exceeds $0.9932$. A cut guarantee $c_d$ on graphs of maximum degree $d$ gives $1-\frac{1-c_d}{6d+12}$, which exceeds $0.9977$ in expectation for $d=3$. A ratio on $T_{H(G)}$ and a cut guarantee are equivalent, so the cut recovered is the Goemans--Williamson or bounded-degree cut used, and the MAX-CUT guarantee is not improved. The main consequence is that on the class $\{T_{H(G)}\}$ of three-occurrence Horn formulas obtained from MAX-CUT instances the proved factor $83/84$ exceeds the Unique Games thresholds $\approx0.94616$ and $\approx0.94017$ that hold for all instances of weighted MAX-HORN-2SAT and of MAX 2-SAT. For a restricted hard-split family with unit vertex rewards and edge-clause weights at least one we obtain $27/28$, and $257/260$ with edge weights four. The Unique Games thresholds of Brakensiek--Huang--Zwick ($\approx0.94616$), Lewin--Livnat--Zwick ($\approx0.94017$) for MAX 2-SAT, and Khot--Kindler--Mossel--O'Donnell ($\approx0.87856$) for MAX-CUT quantify over all instances; the guarantees above concern classes with three occurrences per variable, exceed the first two thresholds, and are consistent with the conjecture. Max-Ones 2-SAT for negative (Horn) formulas equals Maximum Independent Set and Min-Ones 2-SAT for positive formulas equals Minimum Vertex Cover, with the same optima, so the published hardness of these two problems applies to them, and $\operatorname{OPT}(T_H)=4|V|+|E|+\operatorname{MaxOnes}(N_H)$ for the cubic negative formula $N_H$. The Lean~4 development formalizes the formula $T_H$ for every degree and every degree sequence, its score decomposition, repair and optimum identity, the arithmetic transfers, the MAX-CUT clause count and lifting step, and the hard-score optima $4m+\alpha$ and $m+\alpha$; the Goemans--Williamson, Berman--Fujito and Unique Games statements are explicit hypotheses taken from the literature. \end{abstract} \maketitle \section{Introduction} MAX-HORN-2SAT maximizes the number of satisfied unary and binary Horn clauses. We use the polarity convention of MAX~$\{1,2\}$-HORN-SAT in which a clause does not contain two negative literals. A global complementation converts this to the conventional logical definition without changing objective values. Every clause has at most two literals, so each formula is also an instance of MAX~2-SAT, and every guarantee proved below for the Horn class is a guarantee for this class of MAX~2-SAT instances, for cubic graphs, $d$-regular graphs, and non-regular conflict graphs alike. On the class $\{T_{H(G)}\}$ of formulas obtained from the conflict graphs of $d$-regular MAX-CUT instances, Theorem~\ref{thm:cutclass} gives the factor $1-\frac{1-\alpha_\varepsilon}{6d+12}\ge83/84$ for every $d\ge1$, and Theorem~\ref{thm:nonreg-cutclass} extends this conflict-graph guarantee beyond regular base graphs $G$. The construction below starts from cubic Maximum Independent Set (MIS), uses four clones for every graph vertex, and connects them by a directed cycle of implications. One clone participates in a unit clause and the other three in the three incident edge clauses. Each clone additionally occurs in its incoming and outgoing implication. Consequently every formula variable occurs exactly three times. The reduction from cubic MIS to MAX-HORN-2SAT composes unit, edge, and consistency clauses; the quantitative contribution is the exact optimum identity and the explicit cardinality bound of the repair, together with their Lean formalization. The contribution is quantitative rather than merely satisfiability preserving. We prove an explicit repair of every inconsistent clone assignment, obtain an exact affine optimum identity, and transfer the Berman--Fujito cubic-MIS guarantee~\cite{BermanFujito1999} to the Horn class. Cubic MIS is APX-complete~\cite{AlimontiKann2000}, and the same repair proves APX-completeness of the image class. The central result is Theorem~\ref{thm:ugc-class}: the factor $83/84$ on the three-occurrence class $\{T_{H(G)}\}$ lies above the Unique Games thresholds of Brakensiek--Huang--Zwick and Lewin--Livnat--Zwick, which quantify over all instances. Section~\ref{sec:ratio} defines the forced-equality occurrence split with hard implication cycles, which Sections~\ref{sec:hardfam} and~\ref{sec:ugc} use. \section{The cubic three-occurrence construction}\label{sec:cubic} Let $H=(V,E)$ be a finite simple cubic graph, with $n=|V|$ and $m=|E|$. Thus $m=3n/2$. At each vertex $v$, label its incident edges with the three ports $1,2,3$. Introduce four Boolean variables \[ z_{v,0},z_{v,1},z_{v,2},z_{v,3}. \] The formula $T_H$ contains the following clauses. \begin{enumerate} \item For every vertex $v$, one unit clause $(\neg z_{v,0})$. \item For every edge $e=uv$, whose endpoint ports are $p$ at $u$ and $q$ at $v$, one edge clause $(z_{u,p}\vee z_{v,q})$. \item For every vertex $v$ and $i\in\mathbb Z/4\mathbb Z$, one consistency implication $(\neg z_{v,i}\vee z_{v,i+1})$. \end{enumerate} Every clause has at most one negative literal. Every clone occurs in exactly one source clause, one outgoing implication, and one incoming implication; hence it occurs exactly three times. There are $4n$ variables and $n+m+4n=5n+m$ clauses. For an assignment $z$, let \begin{align*} U(z)&=|\{v:z_{v,0}=0\}|,\\ F(z)&=|\{uv\in E:z_{u,p}=z_{v,q}=0\}|,\\ T(z)&=|\{(v,i):z_{v,i}=1,\ z_{v,i+1}=0\}|. \end{align*} These are respectively the satisfied unit clauses, falsified edge clauses, and falsified consistency implications. Therefore \begin{equation}\label{eq:score} \operatorname{val}_{T_H}(z)=U(z)+(m-F(z))+(4n-T(z)). \end{equation} \section{Constructive repair and exact optimum} Call a vertex selected when $z_{v,0}=0$, and clean when it is selected and its four-bit cycle has no $1$-to-$0$ transition. \begin{lemma}[Cycle lemma]\label{lem:cycle} If $z_{v,0}=0$ and the cycle at $v$ has no $1$-to-$0$ transition, then $z_{v,i}=0$ for all $i$. \end{lemma} \begin{proof} A nonconstant cyclic binary word has both a $0$-to-$1$ and a $1$-to-$0$ transition. Since the word begins with zero, absence of a $1$-to-$0$ transition forces it to be constantly zero. \end{proof} Let $C(z)$ be the clean selected vertices. Delete the left endpoint of every edge induced by $C(z)$, ignoring repetitions, and call the remaining set $R(z)$. \begin{lemma}[Quantitative repair]\label{lem:repair} $R(z)$ is independent and \[ |R(z)|\ge \operatorname{val}_{T_H}(z)-(4n+m). \] The set is computable in polynomial time. \end{lemma} \begin{proof} Every edge induced by $C(z)$ loses an endpoint, so $R(z)$ is independent. At most $T(z)$ selected vertices are nonclean, because each such vertex contributes at least one transition. By Lemma~\ref{lem:cycle}, both endpoint clones of every edge induced by $C(z)$ are zero; hence every such edge is counted by $F(z)$. The number of distinct removed endpoints is at most the number of edges induced by $C(z)$, which is at most $F(z)$. Thus \[ |R(z)|\ge U(z)-T(z)-F(z). \] Substituting \eqref{eq:score} gives the claimed inequality. \end{proof} \begin{theorem}[Exact identity]\label{thm:identity} For every simple cubic graph $H$, \[ \operatorname{OPT}(T_H)=4n+m+\alpha(H). \] Moreover, an assignment of value $A$ decodes in polynomial time to an independent set of size at least $A-(4n+m)$. \end{theorem} \begin{proof} The upper bound follows from Lemma~\ref{lem:repair}. For the lower bound, let $I$ be an independent set and set all four clones of $v$ to zero exactly when $v\in I$. Every consistency implication and every edge clause is satisfied, while precisely $|I|$ unit clauses are satisfied. The value is $4n+m+|I|$. Taking $I$ maximum proves equality. \end{proof} \section{The $83/84$ approximation} For a simple cubic graph put $B=4n+m=11n/2$. Every independent set sends all its incident edges to its complement, so $\alpha\le n/2$. If $|I|\ge6\alpha/7$, the ratio $(B+|I|)/(B+\alpha)$ is at least $(11+6/7)/12=83/84$. We give an endpoint argument that only requires the published cubic MIS factor arbitrarily close to $7/6$~\cite{BermanFujito1999}. \begin{theorem}\label{thm:ratio} On the class $\{T_H:H\text{ is simple and cubic}\}$ there is a polynomial-time $83/84$ approximation. \end{theorem} \begin{proof} Return the better lift of two independent sets. First use Berman--Fujito with fixed parameters giving solution fraction $r=6/7-10^{-6}$. If $2\alpha/n\le9999/10000$, then $(83-84r)\alpha\le(11+84\cdot10^{-6})(9999/20000)n \le 11n/2=B$, which gives the required ratio. For the second set, apply the near-satisfiable Max Cut guarantee of Trevisan~\cite{Trevisan}. For fixed $\epsilon=10^{-4}$, a graph having a cut of fraction at least $1-\epsilon$ admits a polynomially computable cut of fraction at least $0.95$ for all sufficiently large $n$: the stated bound is $1-4\sqrt\epsilon+8\epsilon-o(1)>0.95$. Fixed small orders may be solved exhaustively, including the empty graph. The independent set of size $\alpha$ and its complement cut $3\alpha$ edges, a fraction $2\alpha/n$. Thus the cut guarantee applies in the remaining case. From each side delete one endpoint of each internal edge, taking the union of the deletions on that side. The larger remaining independent set has size at least $(n-0.05m)/2=37n/80>3n/7 \ge6\alpha/7$. The endpoint calculation above now applies. The algorithm runs both branches without knowing $\alpha$. \end{proof} \subsection{Generalization to degree $d\ge 3$} The same construction and ratio transfer extend to every fixed degree $d\ge 3$. Let $H=(V,E)$ be simple and $d$-regular, so $m=dn/2$. At each vertex introduce $d+1$ Boolean clones together with one unit clause, $d$ edge clauses (via a port labelling of the incident edges), and a directed cycle of $d+1$ consistency implications. Every clone still occurs in exactly three places. The score identity becomes \[ \operatorname{OPT}(T_H)=(d+1)n+m+\alpha(H). \] The quantitative repair of Lemma~\ref{lem:repair} is independent of the cycle length, and the same deletion argument yields an independent set of size at least $A-((d+1)n+m)$. Write \[ B=(d+1)n+m=n\Bigl(\tfrac{3d}{2}+1\Bigr),\qquad \beta=\tfrac{3d}{2}+1. \] Any independent set cuts exactly $d\alpha$ edges, hence $\alpha\le n/2$. Consequently any independent set of size at least $6\alpha/7$ already produces the ratio \[ \frac{B+|I|}{B+\alpha} \ge\frac{\beta+3/7}{\beta+1/2}. \] The right-hand side is strictly increasing in $\beta$ for $\beta>0$ and equals $83/84$ when $d=3$. Therefore the ratio is at least $83/84$ for every $d\ge 3$. \begin{proposition}\label{prop:degd} Let $H$ be simple and $d$-regular, $d\ge3$, and $B=(d+1)n+m$. \begin{enumerate} \item The assignment with every clone true has value $B$. It is a $\frac{3d+2}{3d+3}$-approximation on $\{T_H\}$. \item If $d\ge27$, then $\frac{3d+2}{3d+3}\ge\frac{83}{84}$. \item If $d\ge22$ and an independent set $I$ satisfies $5\alpha\le(d+3)|I|$, the Berman--Fujito guarantee~\cite{BermanFujito1999}, its lift has value at least $\frac{83}{84}\operatorname{OPT}(T_H)$. \item If an independent set $I$ satisfies $7|I|\ge6\alpha$, its lift has value at least $\frac{21d+20}{21d+21}\operatorname{OPT}(T_H)$. \item If $d=21$, there is a polynomial-time $83/84$ approximation on $\{T_H:H\text{ is simple and $21$-regular}\}$. \item If an independent set $I$ satisfies $28|I|+d\alpha\ge27\alpha$, that is $|I|\ge\rho(d)\alpha$ with $\rho(d)=\frac{27-d}{28}$, its lift has value at least $\frac{83}{84}\operatorname{OPT}(T_H)$. \item For every fixed $\varepsilon>0$ there is a polynomial-time algorithm on $\{T_H:H\text{ is simple and $d$-regular}\}$ whose value is at least $\Bigl(1-\frac{d-2+\varepsilon}{(3d+3)(d+3+\varepsilon)}\Bigr)\operatorname{OPT}(T_H)$. This exceeds $\frac{3d+2}{3d+3}$ for every $d\ge3$, and the limit $\varepsilon\to0$ is $1-\frac{d-2}{3(d+1)(d+3)}$. \end{enumerate} \end{proposition} \begin{proof} With every clone true, the $n$ unit clauses fail and the $m$ edge clauses and all $(d+1)n$ consistency implications hold, so the value is $B$. Since $\alpha\le n/2$ and $2B=(3d+2)n$, we get $B\ge(3d+2)\alpha$, which gives the first claim. For the second, $3d+2\ge83$. For the Berman--Fujito claim, multiply the required inequality $B+84|I|\ge83\alpha$ by $d+3$ and use $(d+3)|I|\ge5\alpha$, $(d+3)B\ge(d+3)(3d+2)\alpha$ and $3d^2-72d+177\ge0$ for $d\ge22$. The fourth claim is the endpoint computation above: using $7|I|\ge6\alpha$, $(21d+21)(B+|I|)-(21d+20)(B+\alpha)\ge B-(3d+2)\alpha\ge0$. For $d=21$ put $a=\alpha/n$, so $B=32.5\,n$ and $m=10.5\,n$. The algorithm returns the better lift of two independent sets, without knowing $a$. The first is a Berman--Fujito set with $\varepsilon=1/50$, which has size at least $50\alpha/241$ since the guarantee for degree $21$ is $24/5+\varepsilon=241/50$. The second is obtained from a cut: solve the Goemans--Williamson semidefinite relaxation of Max Cut on $H$ to additive error $10^{-3}$, round it, and derandomize the rounding by the method of Mahajan and Ramesh~\cite{GoemansWilliamson1995,MahajanRamesh1999}; then delete one endpoint of every edge inside each side, and keep the larger side. If $a\le 99/200$, the first set suffices, because \[ 84\cdot\frac{50}{241}\alpha\ge 83\alpha-B \quad\Longleftrightarrow\quad \frac{15803}{241}\,a\le 32.5, \] and $\frac{15803}{241}\cdot\frac{99}{200}=\frac{1564497}{48200}<32.5$. If $a>99/200$, the independent set of size $\alpha$ cuts $21\alpha$ of the $m$ edges, a fraction $2a>0.99$, so the relaxation has value at least $c=0.989$. By the analysis of Goemans and Williamson, rounding yields expected cut fraction at least $\arccos(1-2c)/\pi$ whenever $c\ge0.845$; this holds because $\arccos(1-2x)/\pi$ is convex on $[1/2,1]$ and its convex minorant coincides with it for $x\ge0.845$. Here $\arccos(-0.978)/\pi>0.93$. Deleting one endpoint of each uncut edge leaves an independent set of size at least $(n-0.07m)/2=(1-0.735)n/2>0.12\,n$ on the larger side. Then $B+84|I|\ge32.5\,n+10.08\,n>41.5\,n\ge83\alpha$, using $\alpha\le n/2$. In both cases $B+84|I|\ge83\alpha$, which is the required ratio. For the sixth claim, $B\ge(3d+2)\alpha$ by the argument of the first claim, and the hypothesis gives $84|I|\ge3(27-d)\alpha$. Adding the two gives $B+84|I|\ge83\alpha$. For the seventh claim, the Berman--Fujito set $I$ with $5\alpha\le(d+3+\varepsilon)|I|$ satisfies $\alpha-|I|\le\frac{d-2+\varepsilon}{d+3+\varepsilon}\alpha$, and $B+\alpha\ge(3d+3)\alpha$, so $\frac{B+|I|}{B+\alpha}=1-\frac{\alpha-|I|}{B+\alpha}\ge1-\frac{d-2+\varepsilon}{(3d+3)(d+3+\varepsilon)}$; the loss is below $\frac1{3d+3}$ because $d-2+\varepsilon\alpha^*$ for $d=3$. Both statements concern bounded-occurrence classes and are consistent with the bounded-occurrence improvements of Ghoshal et al.~\cite{GHLMM2026} and with the Unique Games Conjecture. \section{The forced-equality occurrence split} \label{sec:ratio} Let $F$ be a weighted MAX-HORN-2SAT instance. Its source clauses have nonnegative rational weights. Give every literal occurrence a distinct clone, and replace that occurrence in its source clause by the clone without changing the clause weight. If the occurrences of an original variable $x$ receive clones $x_0,\ldots,x_{d-1}$, add the directed cycle \[ (\neg x_i\vee x_{i+1})\qquad(i\bmod d). \] These implications are \emph{hard}: every feasible assignment must satisfy them. They contribute zero to the maximized objective. This is a partial weighted MAX-HORN-2SAT instance, denoted by $P(F)$. Note that the construction remains faithful even when a source clause contains several occurrences of the same underlying variable, or both polarities of a variable: by Lemma~\ref{lem:hard-cycle}, feasibility forces all clones of a variable to take the same value, so the split clause is satisfied exactly when the source clause is. Every clone appears once in a weighted source clause, once negatively in its outgoing hard implication, and once positively in its incoming hard implication. Thus every clone, viewed as a variable of the split formula $P(F)$, has exactly three occurrences. \begin{lemma}[Hard-cycle consistency]\label{lem:hard-cycle} A clone assignment satisfies every hard implication on one directed cycle if and only if all clones on that cycle have the same value. \end{lemma} \begin{proof} A constant cycle satisfies every implication. Conversely, a nonconstant cyclic binary word has a $1$-to-$0$ transition, and the implication at that transition is false. \end{proof} \begin{theorem}[Exact hard-split identity]\label{thm:hard-split} The transformation $F\mapsto P(F)$ is polynomial, and \[ \operatorname{OPT}_{\mathrm{partial}}(P(F))= \operatorname{OPT}_{\mathrm{weighted}}(F). \] More strongly, feasible split assignments and source assignments have exactly the same attainable objective values under encoding and decoding. \end{theorem} \begin{proof} Lift a source assignment by giving every occurrence clone the value of its original variable. The result satisfies all hard cycles and preserves every source clause's truth value and weight. Conversely, by Lemma~\ref{lem:hard-cycle}, every feasible split assignment is constant on each original-variable cycle. Decode that common value. Again every weighted source clause has the same truth value. Encoding and decoding therefore preserve the objective pointwise, proving both claims. \end{proof} \begin{corollary}[Ratio preservation]\label{cor:ratio-preservation} For every $0\le\rho\le1$, a polynomial-time $\rho$-approximation for the hard three-occurrence image $\{P(F)\}$ yields a polynomial-time $\rho$-approximation for weighted MAX-HORN-2SAT. \end{corollary} \begin{proof} Apply the image-class algorithm and decode its feasible assignment. Both its value and the optimum are unchanged by Theorem~\ref{thm:hard-split}. \end{proof} \section{A hard-split family attaining the target ratio} \label{sec:hardfam} Let $H$ be simple cubic. In the source $F_H(w)$ put a unit clause $(\neg x_v)$ of weight one at each vertex and a clause $(x_u\vee x_v)$ of rational weight $w_e\ge1$ on each edge. Write $W=\sum_e w_e$. Apply the ordinary occurrence split to this source, with zero-score hard cycles. The four ports identify the three edge occurrences and the unit. The source graph can also be recovered by contracting each hard cycle and reading the binary source clauses. \begin{theorem}\label{thm:hard-family} The feasible optimum of $P(F_H(w))$ is $W+\alpha(H)$. For all $w_e\ge1$ there is a polynomial-time $27/28$ approximation. If $W\ge 6n$, this class admits a polynomial-time $257/260>83/84$ approximation. In particular this holds if every edge clause weighs four. \end{theorem} \begin{proof} For the set $S$ of false source variables the score is $W+|S|-\sum_{e\in E(H[S])} w_e$. Delete from $S$ one endpoint of each internal edge, counting repeated deletions only once. The independent set left has size at least $|S|-|E(H[S])|$, which bounds the excess over $W$ from above since $w_e\ge1$. Conversely every independent set realizes $W+|I|$ by setting its variables false and copying this choice to all ports. This proves the identity and the constructive repair. For $n>0$ we have $W\ge m=3n/2\ge3\alpha$. Even a single cubic MIS run with $20|I|\ge17\alpha$ gives $(W+|I|)/(W+\alpha)\ge(3+17/20)/4=77/80>0.94615981$. To attain $27/28$, use both candidates from Theorem~\ref{thm:ratio}. In its near-bipartite case $|I|\ge6\alpha/7$, giving $(3+6/7)/4=27/28$. In its other case $|I|\ge r\alpha$ and $(27-28r)\alpha\le(3+28\cdot10^{-6})(9999/20000)n \le 3n/2\le W$, which is exactly the sufficient inequality. Since $20/17>7/6$, a fixed-parameter Berman--Fujito run gives $20|I|\ge17\alpha$. Here $W\ge6n\ge12\alpha$, so $260(W+|I|)-257(W+\alpha)\ge 3W-36\alpha\ge0$. The empty instance satisfies the division-free bound as well. \end{proof} In Lean, the hard optima $4m+\alpha$ and $m+\alpha$ and the $257/260$ and $77/80$ transfers from a $17/20$ independent set are proved. The $27/28$ statement is the arithmetic implication from the numerical hypothesis $6\alpha\le7s$, or from $20000\alpha\le9999n$ together with $5999993\alpha\le7000000s$, to $28(m+s)\ge27(m+\alpha)$ for an independent set of size $s$. The algorithm that supplies this hypothesis is the Berman--Fujito and Trevisan branch proved in the text above and is not formalized in Lean. A second Lean statement makes the two branch guarantees explicit: if $20000\alpha\le9999n$ implies $5999993\alpha\le7000000s$ (Berman--Fujito branch) and $20000\alpha>9999n$ implies $37n\le80s$ (near-bipartite branch), then $28(m+s)\ge27(m+\alpha)$. \paragraph{Why hardening can change the ratio.} In the unit-weight version, take four disjoint copies of the cube $Q_3$. Each has independence number four by its parity classes and a perfect matching. Take a parity class in each of three copies and an antipodal pair in the fourth. The pair is maximal because every other vertex neighbors an endpoint. Thus $|I|=14$, $\alpha=16$, $n=32$, and $m=48$. The same feasible lift meets $7|I|\ge6\alpha$ and scores $190/192$ relative to optimum on $T_H$, but only $62/64$ on $P(F_H(1))$. The $128$ satisfied implications have ceased to earn points. This refutes a transfer based solely on the MIS guarantee and this decoding, even for maximal sets with perfectly consistent ports. \section{A signed graph for general weighted inputs} The unsigned construction can fail even on $K_4$. Start with two indexed copies of $(x\vee x)$, assign their occurrences the opposite pairs of a four-cycle, and join each source pair. The resulting graph is simple cubic. Each singleton is a maximum independent set and gives a nonconstant cyclic word. For an example with distinct variables within each clause, three indexed copies of $(x\vee y)$ give two triangles joined by a matching. An independent set taking a vertex in each triangle at different indices is maximum and violates both cycles under membership decoding. In the unsigned graph a pair edge forbids only simultaneous membership. Complementation reverses a directed implication but does not turn it into a prohibition on simultaneous membership. The paper uses the at-most-one-negative convention. \paragraph{Unary terminals.} For the path $a$--$w$--$b$, the terminal states $00$, $01$, $10$, and $11$ give maximum total cardinalities $1,1,1,2$. It realizes a one-unit bonus for $11$ when another constraint synchronizes the ends. Both mixed states extend to independent sets. The following signed construction instead gives a unit clause one reward vertex attached to its falsifying port. \begin{theorem}\label{thm:signed} For any weighted source $F$ of width at most two, let $D$ be its number of literal occurrences, $W$ its total nonnegative clause weight, and $M=W+1$. One can construct a simple vertex-weighted graph $J$ of maximum degree three such that $\alpha_w(J)=DM+\operatorname{OPT}(F)$. Every independent set of weight $A$ decodes in polynomial time to a feasible split assignment of score at least $A-DM$. \end{theorem} \begin{proof} At occurrence $i$ create adjacent ports $T_i,F_i$ of weight $M$. Join $T_i$ to $F_{i+1}$ around each variable cycle. For a singleton cycle the pair edge already supplies this conflict; insert it just once. Discard variables with no occurrences. For each literal occurrence create a reward vertex of weight equal to its clause weight and join it to the port that falsifies that literal. Join the two reward vertices of each binary clause. Every port has at most two ring neighbors and one reward neighbor. Distinct literal occurrences have distinct vertices even for repeated literals. The graph has $3D$ vertices, linear combinatorial size and polynomial bit complexity with binary rational weights. At most one port per pair and one reward per clause can be selected. If fewer than $D$ ports are selected, the weight is at most $(D-1)M+W0$~\cite{BrakensiekHuangZwick2024}. In particular, $19/20=0.95>\alpha^*$. A deterministic polynomial-time algorithm returning value at least $19\operatorname{OPT}(F)/20$ on \emph{every} weighted source $F$ would solve the UG-hard gap problem in polynomial time and, assuming UGC, imply $\mathrm P=\mathrm{NP}$. By Theorem~\ref{thm:hard-split} the same implication holds for a guarantee on the entire hard-split image. The worst-case bounds in Theorems~\ref{thm:ratio} and~\ref{thm:hard-family} concern their specified cubic families. The constant $\beta^\star\approx0.94016567$ of Lewin, Livnat and Zwick is the UG-hard threshold for MAX~2-SAT~\cite{BrakensiekHuangZwick2024}. Both UG-hardness statements quantify over all instances. They give no information about the class in which every variable has exactly three literal occurrences. For that class Theorem~\ref{thm:ratio} gives the worst-case ratio $83/84$, and \[ \frac{83}{84}>0.94615981>0.94016567 . \] Ghoshal, Huang, Lee, Makarychev and Makarychev prove that MAX~2-SAT instances in which every variable appears in at most $d$ constraints admit a $\beta^\star+\tilde\Omega(1/d^{2})$-approximation~\cite{GHLMM2026}. Thus a guarantee above $\beta^\star$ on a bounded-occurrence class is established for every fixed $d$ and is consistent with the Unique Games Conjecture. A guarantee above $\alpha^*$ or $\beta^\star$ on \emph{all} instances would not be. For MAX~2-SAT instances in which every variable appears in at most two clauses, the problem can be solved exactly in linear time, while already three occurrences per variable give an NP-complete problem~\cite{RamanRavikumarRao1998}. Thus the occurrence bound $d=3$ is the first at which the problem is NP-hard, and for every fixed $d$ the guarantee of~\cite{GHLMM2026} exceeds $\beta^\star$. The endpoint guarantee obtained from a $6/7$-approximate independent set on a $d$-regular graph is \[ r(d)=\frac{21d+20}{21d+21}, \] which is strictly increasing for $d\ge3$ since \[ r(d+1)-r(d)=\frac{21}{(21d+21)(21d+42)}>0 . \] For $d=3$ the independent-set hypothesis is supplied by Theorem~\ref{thm:ratio}, and $r(3)=83/84$ exceeds $\beta^\star$ by $\approx0.04793$. For every $d\ge6$ Proposition~\ref{prop:degd}(1) gives the unconditional factor $\frac{3d+2}{3d+3}>0.95>\alpha^*>\beta^\star$ on the $d$-regular family. For $d\ge3$ one has $\frac{d-2}{3(d+1)(d+3)}\le\frac4{189}<0.022$, because $63(d-2)\le4(d+1)(d+3)$ is equivalent to $(4d-23)(d-6)\ge0$, which holds for every integer $d$. Hence for every $d\ge4$ and every sufficiently small $\varepsilon>0$ the factor of Proposition~\ref{prop:degd}(7) exceeds $0.97>\alpha^*>\beta^\star$ on the $d$-regular family, and together with $r(3)=83/84$ every class $\{T_H:H\text{ is simple and $d$-regular}\}$ with $d\ge3$ has a polynomial-time factor above $\alpha^*$. These are statements about three-occurrence classes and do not concern all instances. The additive gain $\tilde\Omega(1/d^{2})$ of~\cite{GHLMM2026} is $o(1)$ in $d$. For the hard-split family with $d=3$ the proved ratios are those of Theorems~\ref{thm:hard-split} and~\ref{thm:hard-family}. By Proposition~\ref{prop:degd}(6), for each $d$ with $4\le d\le20$ an independent-set algorithm of ratio $\rho(d)=(27-d)/28$ on $d$-regular graphs would give $83/84$ on the $d$-regular family, and $83/84>\alpha^*>\beta^\star$. The thresholds of Brakensiek, Huang and Zwick quantify over all instances. OpenAI released on 6~October 2026 a manuscript claiming a proof of the Unique Games Conjecture, together with a Lean formalization; this claim has not been peer reviewed~\cite{OpenAIMath2026}. If it is confirmed, the UG-hardness statements above become NP-hardness statements. \subsection{MAX-CUT as MAX 2-SAT} \begin{proposition}\label{prop:cut2sat} Let $G=(V,E)$ be a graph with $n$ vertices and $m$ edges. Let $F_G$ be the formula with one variable $x_v$ for every vertex and, for every edge $uv$, the two clauses $(x_u\lor x_v)$ and $(\lnot x_u\lor\lnot x_v)$. Then: \begin{enumerate} \item an assignment $z$ satisfies exactly $m+\operatorname{cut}(S_z)$ clauses, where $S_z=\{v:z(x_v)=\text{true}\}$ and $\operatorname{cut}(S)$ is the number of edges with exactly one endpoint in $S$; hence $\operatorname{OPT}(F_G)=m+\operatorname{maxcut}(G)$; \item the variable $x_v$ occurs in exactly $2\deg(v)$ clauses; \item if an assignment satisfies at least $\rho\operatorname{OPT}(F_G)$ clauses, then the cut $S_z$ has at least $\rho\,(m+\operatorname{maxcut}(G))-m$ edges. \end{enumerate} \end{proposition} \begin{proof} For an edge $uv$ whose endpoints receive different values both clauses hold. If both endpoints are true only $(x_u\lor x_v)$ holds, and if both are false only $(\lnot x_u\lor\lnot x_v)$ holds. Summing over the edges gives the first claim, and the second and third follow. \end{proof} The clause $(\lnot x_u\lor\lnot x_v)$ has two negative literals, so $F_G$ is an instance of MAX~2-SAT that does not belong to the Horn class; no guarantee of this paper is claimed for it. \begin{proposition}\label{prop:cutconflict} Let $G$ be a simple $d$-regular graph with $n$ vertices and $m=dn/2$ edges. Let $H$ be the conflict graph of $F_G$: its $N=4m$ vertices are the literal occurrences of $F_G$, and two vertices are adjacent if they lie in the same clause or are complementary literals. Then $H$ is simple and $(d+1)$-regular, and \[ \alpha(H)=\operatorname{OPT}(F_G)=m+\operatorname{maxcut}(G). \] Consequently, with $D=d+1$, $M=DN/2$ and $B=(D+1)N+M=2m(3d+5)$, the formula $T_H$ satisfies $\operatorname{OPT}(T_H)=B+m+\operatorname{maxcut}(G)$, and an assignment of $T_H$ of value $A$ yields in polynomial time a cut of $G$ with at least $A-B-m$ edges. \end{proposition} \begin{proof} Every literal occurrence has exactly one neighbour in its clause. A positive occurrence of $x_u$ is adjacent to the $d$ negative occurrences of $x_u$, and symmetrically; an in-clause neighbour is a literal of another variable, so no edge is repeated. Hence $H$ is simple and $(d+1)$-regular. An independent set contains at most one literal of each clause and no two complementary literals, so it is a consistent partial assignment satisfying as many clauses as the set has vertices; conversely, an assignment and one satisfied literal per satisfied clause give an independent set. Thus $\alpha(H)=\operatorname{OPT}(F_G)$, which equals $m+\operatorname{maxcut}(G)$ by Proposition~\ref{prop:cut2sat}. The identity for $T_H$ is the degree-$D$ exact identity. By the quantitative repair, an assignment of value $A$ gives an independent set of size at least $A-B$, hence an assignment of $F_G$ satisfying at least $A-B$ clauses, hence a cut with at least $A-B-m$ edges by Proposition~\ref{prop:cut2sat}. \end{proof} \begin{corollary}\label{cor:cutratio} Let $\operatorname{maxcut}(G)=\gamma m$ and $0\le\rho\le1$. \begin{enumerate} \item If an assignment of $F_G$ satisfies at least $\rho\operatorname{OPT}(F_G)$ clauses, its cut has at least $\bigl(\rho-\frac{1-\rho}{\gamma}\bigr)\operatorname{maxcut}(G)$ edges. \item If $G$ is $d$-regular and an assignment of $T_H$ has value at least $\rho\operatorname{OPT}(T_H)$, the cut obtained from it has at least $\bigl(\rho-\frac{(1-\rho)(6d+11)}{\gamma}\bigr)\operatorname{maxcut}(G)$ edges. \end{enumerate} \end{corollary} \begin{proof} By Proposition~\ref{prop:cut2sat}, the cut has at least $\rho(m+\gamma m)-m$ edges; dividing by $\gamma m$ gives the first claim. By Proposition~\ref{prop:cutconflict} it has at least $\rho(B+m+\gamma m)-B-m$ edges with $B+m=(6d+11)m$, which gives the second. \end{proof} \begin{theorem}\label{thm:cutclass} For every $d\ge1$ there is a polynomial-time algorithm that, given a simple $d$-regular graph $G$, returns an assignment of $T_{H(G)}$ of value at least \[ \Bigl(1-\frac{1-\alpha_\varepsilon}{6d+12}\Bigr)\operatorname{OPT}(T_{H(G)})\ \ge\ \frac{83}{84}\operatorname{OPT}(T_{H(G)}), \] where $H(G)$ is the conflict graph of Proposition~\ref{prop:cutconflict} and $\alpha_\varepsilon\approx0.87856$ Here $\alpha_\varepsilon=\alpha_{\mathrm{GW}}-10^{-5}\ge0.8785$, where $\alpha_{\mathrm{GW}}\approx0.87856$ is the Goemans--Williamson constant. \end{theorem} \begin{proof} Let $c=\operatorname{maxcut}(G)$. Solving the Goemans--Williamson relaxation to additive error $10^{-5}$ and rounding with derandomization~\cite{GoemansWilliamson1995,MahajanRamesh1999} returns in polynomial time a set $S$ with $\operatorname{cut}(S)\ge\alpha_\varepsilon\,c$ (the relaxation error $10^{-5}$ is absorbed in $\alpha_\varepsilon$). Set $x_v$ true exactly for $v\in S$ and choose one true literal in every satisfied clause of $F_G$. These $m+\operatorname{cut}(S)$ literal occurrences are pairwise non-adjacent in $H(G)$, because they lie in distinct clauses and no two are complementary. So they form an independent set $I$ with $|I|=m+\operatorname{cut}(S)$, while $\alpha(H(G))=m+c$ by Proposition~\ref{prop:cutconflict}. Since $c\le m$, \[ |I|\ge m+\alpha_\varepsilon\,c\ge\frac{1+\alpha_\varepsilon}{2}\,(m+c)=\frac{1+\alpha_\varepsilon}{2}\,\alpha(H(G)), \] because $(1-\alpha_\varepsilon)(m-c)\ge0$. Let $D=d+1$, so $H(G)$ is $D$-regular and $B=(D+1)N+M\ge(3D+2)\alpha(H(G))$ by $\alpha(H(G))\le N/2$. The lift of $I$ has value $B+|I|$, hence \[ \frac{B+|I|}{B+\alpha(H(G))}\ge1-\frac{\frac{1-\alpha_\varepsilon}{2}\,\alpha(H(G))}{B+\alpha(H(G))}\ge1-\frac{1-\alpha_\varepsilon}{6d+12}. \] Finally $\frac{1-\alpha_\varepsilon}{6d+12}\le\frac{1-\alpha_\varepsilon}{18}<\frac{1}{84}$ for $d\ge1$, since $1-\alpha_\varepsilon\le0.1215<18/84\approx0.214$. \end{proof} \begin{proposition}\label{prop:gamma-ratio} Let $G$ be $d$-regular with $\operatorname{maxcut}(G)=\gamma m$, $\tfrac12\le\gamma\le1$. Let $h$ be the largest convex function on $[0,1]$ with $h(x)\le\frac1\pi\arccos(1-2x)$; thus $h(x)=\alpha_{\mathrm{GW}}x$ for $x\le x^*\approx0.8446$ and $h(x)=\frac1\pi\arccos(1-2x)$ for $x\ge x^*$. The Goemans--Williamson algorithm returns in polynomial time a cut $S$ with $\operatorname{cut}(S)\ge(h(\gamma)-10^{-5})m$, and the lift of the corresponding independent set of $H(G)$ has on $T_{H(G)}$ the ratio at least \[ 1-\frac{\gamma-h(\gamma)+10^{-5}}{6d+11+\gamma}\ \ge\ 1-\frac{0.1053}{6d+11.5}. \] The cut fraction that Corollary~\ref{cor:cutratio}(2) recovers from this ratio equals $(h(\gamma)-10^{-5})/\gamma$. \end{proposition} \begin{proof} Let $x_e\in[0,1]$ be the semidefinite value of the edge $e$ and $s=\sum_ex_e\ge\gamma m$ (up to the additive error $10^{-5}m$). The expected cut of hyperplane rounding is $\sum_e\frac1\pi\arccos(1-2x_e)\ge\sum_eh(x_e)\ge m\,h(s/m)\ge m\,h(\gamma)$ by convexity and monotonicity of $h$, and the derandomization of~\cite{MahajanRamesh1999} preserves it. By Proposition~\ref{prop:cutconflict} $\alpha(H(G))=m+\gamma m$, and $B=(6d+10)m$, so the value of the lift is $B+m+\operatorname{cut}(S)$ against the optimum $B+m+\gamma m=(6d+11+\gamma)m$, which gives the first bound. On $[\frac12,1]$ the function $\gamma-h(\gamma)$ is maximal where $\gamma(1-\gamma)=\pi^{-2}$, that is at $\gamma^*=\frac12\bigl(1+\sqrt{1-4/\pi^2}\bigr)\approx0.8856$, with $\gamma^*-h(\gamma^*)\approx0.10526$. Since $6d+11+\gamma\ge6d+11.5$, the second bound follows. For the last claim, with $1-\rho=\frac{\gamma-\hat h}{6d+11+\gamma}$ and $\hat h=h(\gamma)-10^{-5}$, \[ \rho-\frac{(1-\rho)(6d+11)}{\gamma}=1-\frac{(1-\rho)(6d+11+\gamma)}{\gamma}=1-\frac{\gamma-\hat h}{\gamma}=\frac{\hat h}{\gamma}. \qedhere \] \end{proof} \begin{remark}\label{rem:gamma-linear} With the linear bound $\operatorname{cut}(S)\ge\alpha_\varepsilon\gamma m$ the lift has on $T_{H(G)}$ the ratio $\rho_d(\gamma)=\frac{6d+11+\alpha_\varepsilon\gamma}{6d+11+\gamma}=1-\frac{(1-\alpha_\varepsilon)\gamma}{6d+11+\gamma}$, and Corollary~\ref{cor:cutratio}(2) applied to $\rho_d(\gamma)$ gives the cut fraction $1-\frac{(1-\alpha_\varepsilon)\gamma}{6d+11+\gamma}-\frac{(1-\alpha_\varepsilon)(6d+11)}{6d+11+\gamma}=\alpha_\varepsilon$ for every $\gamma\in(0,1]$. The algorithm does not use $\gamma$. Since $\sup_{0<\gamma\le1}\frac{(1-\alpha_\varepsilon)\gamma}{6d+11+\gamma}=\frac{1-\alpha_\varepsilon}{6d+12}$, the ratio $1-\frac{1-\alpha_\varepsilon}{6d+12}$ holds for every $G$, while the instance ratio $\rho_d(\gamma)$ recovers the constant $\alpha_\varepsilon$ exactly. Moreover $\rho_d(\gamma)-\alpha_\varepsilon=\frac{(1-\alpha_\varepsilon)(6d+11)}{6d+11+\gamma}>0$, so $\rho_d(\gamma)>\alpha_\varepsilon$ for every $\gamma\in(0,1]$. Proposition~\ref{prop:gamma-ratio} replaces $\alpha_\varepsilon\gamma$ by $h(\gamma)-10^{-5}\ge\alpha_\varepsilon\gamma$. \end{remark} \begin{proposition}\label{prop:bounded-cut} Let $c_d\in(0,1]$ and suppose a polynomial-time algorithm returns on every graph of maximum degree $d$ a cut with at least $c_d\operatorname{maxcut}(G)$ edges; if the algorithm is randomized and the guarantee is for the expected cut, every statement below is for the expected value. Then on $\{T_{H(G)}:G\text{ is }d\text{-regular}\}$ a polynomial-time algorithm has the ratio at least $1-\frac{1-c_d}{6d+12}$. \end{proposition} \begin{proof} As in the proof of Theorem~\ref{thm:cutclass} with $0.8785$ replaced by $c_d$: $|I|\ge\frac{1+c_d}{2}\alpha(H(G))$ and $B+\alpha(H(G))\ge(3D+3)\alpha(H(G))$ with $D=d+1$, so the loss is at most $\frac{1-c_d}{2(3d+6)}$. \end{proof} For graphs of maximum degree $d$, Feige, Karpinski and Langberg give a guarantee $\alpha_{\mathrm{GW}}+\epsilon_d$ with $\epsilon_d>0$, and $0.921$ for $d=3$~\cite{FeigeKarpinskiLangberg2002}; Halperin, Livnat and Zwick give an algorithm whose expected approximation ratio on graphs of maximum degree $3$ is at least $0.9326$~\cite{HalperinLivnatZwick2004}; Hsieh and Kothari give $\alpha_{\mathrm{GW}}+\tilde\Omega(1/d^2)$~\cite{HsiehKothari2023}. With $c_3=0.9326$ as an expected guarantee, Proposition~\ref{prop:bounded-cut} gives the expected ratio $1-\frac{0.0674}{30}>0.9977$ on $\{T_{H(G)}:G\text{ cubic}\}$. These bounded-degree guarantees exceed $\alpha_{\mathrm{GW}}$ on a class of graphs and are consistent with the threshold of~\cite{KKMO2007}, which quantifies over all graphs. \begin{remark}\label{rem:cutclass-range} Theorem~\ref{thm:cutclass} applies to every degree $D=d+1$ with $4\le D\le20$, that is $3\le d\le19$, on the class $\{T_{H(G)}:G\text{ is }(D-1)\text{-regular}\}$. In that range $|I|\ge\frac{1+\alpha_\varepsilon}{2}\,\alpha(H(G))$ exceeds $\rho(D)=\frac{27-D}{28}\le\frac{23}{28}$, so Proposition~\ref{prop:degd}(6) gives the ratio $83/84$ without any assumption on an independent-set algorithm. Since $\frac{1+\alpha_\varepsilon}{2}>6/7$, Proposition~\ref{prop:degd}(4) gives the ratio $\frac{21D+20}{21D+21}$, which equals $\frac{104}{105}$ for $D=4$ and $\frac{440}{441}$ for $D=20$. For these $G$ the constant of Corollary~\ref{cor:cutratio} is $B+m=(6D+5)m$; for $D=4$ it equals $29m$, and an assignment of $T_{H(G)}$ of ratio $\frac{104}{105}$ yields a cut with at least $\frac{104}{105}\operatorname{maxcut}(G)-\frac{29}{105}m$ edges, which is $\frac{49}{105}m$ when $\operatorname{maxcut}(G)=\frac34m$. The statement concerns the conflict-graph class; for arbitrary $D$-regular graphs $H$ with $4\le D\le20$ the ratio $83/84$ is given by Proposition~\ref{prop:degd}(6) under the hypothesis stated there. \end{remark} \subsection{Generalization to arbitrary simple graphs} The three-occurrence construction extends without change of method to any finite simple graph $H=(V,E)$ with $n=|V|$ and $m=|E|$, even when $H$ is not regular. At each vertex $v\in V$ of degree $d_v=\deg_H(v)$, label its incident edges with the ports $1,\ldots,d_v$ and introduce $d_v+1$ Boolean variables \[ z_{v,0},z_{v,1},\ldots,z_{v,d_v}. \] The formula $T_H$ contains: \begin{enumerate} \item for every vertex $v\in V$, one unit clause $(\neg z_{v,0})$; \item for every edge $e=uv\in E$ with endpoint ports $p$ at $u$ and $q$ at $v$, one edge clause $(z_{u,p}\vee z_{v,q})$; \item for every vertex $v\in V$ and $i\in\mathbb{Z}/(d_v+1)\mathbb{Z}$, one consistency implication $(\neg z_{v,i}\vee z_{v,i+1})$. \end{enumerate} Every clause has at most one negative literal. Each clone $z_{v,i}$ occurs once in a source clause (the unit clause at $v$ for $i=0$, or the edge clause at port $i$ for $1\le i\le d_v$), once negatively in $(\neg z_{v,i}\vee z_{v,i+1})$, and once positively in $(\neg z_{v,i-1}\vee z_{v,i})$. Thus every variable of $T_H$ still has exactly three literal occurrences. Using $\sum_{v\in V} d_v = 2m$, the total number of variables is \[ \sum_{v\in V}(d_v+1) = n+2m, \] and the total number of clauses is $n + m + (n+2m) = 2n+3m$. Put \[ B(H) = \sum_{v\in V}(d_v+1) + m = n + 3m. \] \begin{lemma}[General quantitative repair and exact identity]\label{lem:general-identity} For every finite simple graph $H=(V,E)$ with $n=|V|$ and $m=|E|$, \[ \operatorname{OPT}(T_H) = n + 3m + \alpha(H). \] Moreover, every assignment $z$ of value $A$ decodes in polynomial time to an independent set $R(z)\subseteq V$ of size at least $A-(n+3m)$. \end{lemma} \begin{proof} For an assignment $z$, let $U(z)=|\{v\in V: z_{v,0}=0\}|$, let $F(z)$ be the number of falsified edge clauses, and let $T(z)=\sum_{v\in V}|\{i\in\mathbb{Z}/(d_v+1)\mathbb{Z}: z_{v,i}=1,\ z_{v,i+1}=0\}|$. Since there are $n+2m$ consistency implications in total, \[ \operatorname{val}_{T_H}(z) = U(z) + (m - F(z)) + (n + 2m - T(z)) = n + 3m + U(z) - F(z) - T(z). \] Call a vertex $v\in V$ selected when $z_{v,0}=0$, and clean when it is selected and its $(d_v+1)$-bit cycle has no $1$-to-$0$ transition. By Lemma~\ref{lem:cycle} (which holds for any cycle length $d_v+1\ge 1$), every clone $z_{v,i}$ of a clean selected vertex $v$ is zero. Let $C(z)$ be the set of clean selected vertices, and form $R(z)$ by deleting one endpoint of each edge induced by $C(z)$, ignoring repeated deletions. Then $R(z)$ is independent in $H$. Each nonclean selected vertex contributes at least one $1$-to-$0$ transition, so at most $T(z)$ selected vertices are nonclean. Every edge induced by $C(z)$ has both endpoint clones equal to zero and is therefore counted by $F(z)$, so at most $F(z)$ vertices are removed from $C(z)$. Consequently, \[ |R(z)| \ge |C(z)| - F(z) \ge U(z) - T(z) - F(z) = \operatorname{val}_{T_H}(z) - (n+3m). \] This gives the constructive repair and the upper bound $\operatorname{OPT}(T_H)\le n+3m+\alpha(H)$. Conversely, for any independent set $I\subseteq V$, setting $z_{v,i}=0$ for all $v\in I$ and $0\le i\le d_v$, and $z_{v,i}=1$ otherwise, satisfies all $n+2m$ consistency implications, all $m$ edge clauses, and $|I|$ unit clauses, realizing value $n+3m+|I|$. Taking $I$ maximum yields equality. \end{proof} \begin{theorem}[Non-regular conflict-graph family]\label{thm:nonreg-cutclass} Let $G=(V_G,E_G)$ be any finite simple graph with $m=|E_G|\ge 1$ edges and no isolated vertices, and let $H(G)$ be the conflict graph of $F_G$ from Proposition~\ref{prop:cutconflict}. Then every variable of $T_{H(G)}$ has exactly three literal occurrences, and there is a polynomial-time algorithm returning an assignment of $T_{H(G)}$ of value at least \[ \Bigl(1 - \frac{1-\alpha_\varepsilon}{18}\Bigr)\operatorname{OPT}(T_{H(G)}) > 0.9932\,\operatorname{OPT}(T_{H(G)}). \] \end{theorem} \begin{proof} Each vertex $v\in V_G$ of degree $d_v=\deg_G(v)\ge 1$ contributes $d_v$ positive literal occurrences and $d_v$ negative literal occurrences to $F_G$. Thus $H(G)$ has $N = 2\sum_{v\in V_G} d_v = 4m$ vertices. Every literal occurrence in $F_G$ has $1$ in-clause neighbor and $d_v$ complementary neighbors in $H(G)$ (with no overlap, as in Proposition~\ref{prop:cutconflict}), so those $2d_v$ vertices each have degree $d_v+1$ in $H(G)$. Hence the number of edges of $H(G)$ is \[ M = |E(H(G))| = \frac{1}{2}\sum_{v\in V_G} 2d_v(d_v+1) = \sum_{v\in V_G}(d_v^2 + d_v) = 2m + \sum_{v\in V_G} d_v^2. \] Since $d_v\ge 1$ for every $v\in V_G$, we have $d_v^2 \ge d_v$, so $\sum_{v\in V_G} d_v^2 \ge \sum_{v\in V_G} d_v = 2m$ and therefore $M \ge 4m$. By Lemma~\ref{lem:general-identity}, \[ \operatorname{OPT}(T_{H(G)}) = B(H(G)) + \alpha(H(G)), \qquad B(H(G)) = N + 3M \ge 4m + 12m = 16m. \] On the other hand, as in Proposition~\ref{prop:cutconflict}, an independent set in $H(G)$ selects at most one literal per clause of $F_G$ and no complementary pair, so $\alpha(H(G)) = \operatorname{OPT}(F_G) = m + \operatorname{maxcut}(G) \le 2m$. Consequently, $B(H(G)) \ge 16m \ge 8\,\alpha(H(G))$. Now run the derandomized Goemans--Williamson algorithm~\cite{GoemansWilliamson1995,MahajanRamesh1999} on $G$ to obtain in polynomial time a cut $S$ with $\operatorname{cut}(S)\ge \alpha_\varepsilon\,\operatorname{maxcut}(G)$. Selecting one true literal per satisfied clause of $F_G$ under $S$ yields an independent set $I$ in $H(G)$ of size $|I| = m + \operatorname{cut}(S)$. Because $\operatorname{maxcut}(G)\le m$, we have $(1-\alpha_\varepsilon)(m-\operatorname{maxcut}(G))\ge 0$, and hence \[ |I| \ge m + \alpha_\varepsilon\,\operatorname{maxcut}(G) \ge \frac{1+\alpha_\varepsilon}{2}\bigl(m + \operatorname{maxcut}(G)\bigr) = \frac{1+\alpha_\varepsilon}{2}\,\alpha(H(G)). \] Lifting $I$ to $T_{H(G)}$ gives an assignment of value $B(H(G)) + |I|$, whose approximation ratio is \begin{align*} \frac{B(H(G)) + |I|}{B(H(G)) + \alpha(H(G))} &= 1 - \frac{\alpha(H(G)) - |I|}{B(H(G)) + \alpha(H(G))} \\ &\ge 1 - \frac{\frac{1-\alpha_\varepsilon}{2}\,\alpha(H(G))}{9\,\alpha(H(G))} \\ &= 1 - \frac{1-\alpha_\varepsilon}{18} \\ &> 0.9932. \qedhere \end{align*} \end{proof} \subsection{Consequences of the MAX-CUT reduction for the Unique Games Conjecture} Khot, Kindler, Mossel and O'Donnell show that, assuming the Unique Games Conjecture, MAX-CUT cannot be approximated in polynomial time within any constant above $\alpha_{\mathrm{GW}}=\min_{0\alpha^*\approx0.94616>\beta^\star\approx0.94017 . \] Under the Unique Games Conjecture no polynomial-time algorithm has a factor above $\alpha^*+\varepsilon$ on all instances of weighted MAX~$\{1,2\}$-HORN-SAT, or above $\beta^\star+\varepsilon$ on all instances of MAX~2-SAT, for any $\varepsilon>0$. The class $\{T_{H(G)}\}$ is a class of Horn formulas, hence of MAX~2-SAT instances, in which every variable has exactly three literal occurrences, and it is consistent with the conjecture. \end{theorem} \begin{proof} The algorithm and the factor $83/84$ are Theorem~\ref{thm:cutclass}. The numerical inequalities and the hardness statements are those quoted in the first paragraph of Section~\ref{sec:ugc} and~\cite{BrakensiekHuangZwick2024}. \end{proof} Take the ratio $\rho_d=1-\frac{1-\alpha_\varepsilon}{6d+12}$ of Theorem~\ref{thm:cutclass}, which does not depend on $\gamma$. Then the cut fraction guaranteed by Corollary~\ref{cor:cutratio}(2) is \[ 1-\frac{1-\alpha_\varepsilon}{6d+12}\Bigl(1+\frac{6d+11}{\gamma}\Bigr)\le1-\frac{1-\alpha_\varepsilon}{6d+12}\,(6d+12)=\alpha_\varepsilon, \] with equality exactly for $\gamma=1$. This is a lower bound valid for every $\gamma\in(0,1]$ that uses only the value $\rho_d$; it is the worst case over $\gamma$ of the corollary and is not a property of the algorithm. The algorithm does not obtain its cut from $\rho_d$. It first computes $S$ with $\operatorname{cut}(S)\ge\alpha_\varepsilon\operatorname{maxcut}(G)$ and then lifts the independent set $I$ of size $m+\operatorname{cut}(S)$ of Theorem~\ref{thm:cutclass}. For this lift the instance ratio is $\rho_d(\gamma)=\frac{6d+11+\alpha_\varepsilon\gamma}{6d+11+\gamma}>\alpha_\varepsilon$ by Remark~\ref{rem:gamma-linear}, and Corollary~\ref{cor:cutratio}(2) applied to $\rho_d(\gamma)$ returns exactly the cut fraction $\alpha_\varepsilon$ of the cut $S$. The MAX-CUT guarantee is thus the one of~\cite{GoemansWilliamson1995,MahajanRamesh1999}, and the reduction transfers it to a guarantee on $T_{H(G)}$ that exceeds $\alpha^*$. A bounded-degree cut guarantee $c_d$ enters only through Proposition~\ref{prop:bounded-cut}. Lean proves the clause-count identity $m+\operatorname{cut}(S)$ and the arithmetic of Corollary~\ref{cor:cutratio} (\texttt{CutTransfer}), the division-free inequality behind Proposition~\ref{prop:gamma-ratio} (\texttt{CutTransfer}, \texttt{gap\_ratio}), the strict inequality $\rho_d(\gamma)>\alpha_\varepsilon$ of Remark~\ref{rem:gamma-linear} in division-free form (\texttt{CutTransfer}, \texttt{lifted\_ratio\_gt\_gw}), the lifting step with $18785\,\alpha(H)\le20000\,|I|$, which follows from $|I|\ge\frac{1+\alpha_\varepsilon}{2}\alpha(H)$ (\texttt{CutLift}), and the degree-dependent identity and ratio step for non-regular graphs together with the arithmetic $8\alpha\le B$ of Theorem~\ref{thm:nonreg-cutclass} (\texttt{GeneralDegreeFormula}) and the count $M\ge4m$ (\texttt{ConflictDegree}), and the division-free form of Proposition~\ref{prop:bounded-cut} (\texttt{CitedResults}). The Goemans--Williamson guarantee and the Khot--Kindler--Mossel--O'Donnell threshold are taken from the literature (\texttt{CitedResults}) and are not formalized. \section{Max-Ones and Min-Ones 2-SAT}\label{sec:ones} In Max-Ones (respectively Min-Ones) 2-SAT one is given a 2-CNF formula and must find a satisfying assignment with the largest (respectively smallest) number of true variables. Write $\operatorname{ones}(a)$ for the number of true variables of an assignment $a$. \subsection{Negative formulas and independent sets} A \emph{negative} 2-CNF formula has only clauses $(\neg x_u\vee\neg x_v)$ and $(\neg x_u)$; it is a Horn formula. Let $Z$ be the set of variables with a unit clause and let $G_\varphi$ be the graph on the variables outside $Z$ with an edge $uv$ for every clause $(\neg x_u\vee\neg x_v)$ with $u,v\notin Z$. Clauses meeting $Z$ are satisfied by every assignment that is false on $Z$. \begin{lemma}\label{lem:neg-ones} An assignment satisfies a negative 2-CNF formula $\varphi$ if and only if it is false on $Z$ and its set of true variables is an independent set of $G_\varphi$. Hence $\operatorname{MaxOnes}(\varphi)=\alpha(G_\varphi)$, and a satisfying assignment with $k$ true variables is the same object as an independent set of size $k$. \end{lemma} \begin{proof} A clause $(\neg x_u\vee\neg x_v)$ with $u,v\notin Z$ is falsified exactly when both $x_u$ and $x_v$ are true, that is, when $u,v$ are adjacent true variables. A unit clause $(\neg x_u)$ is falsified exactly when $x_u$ is true. The remaining clauses contain a variable of $Z$ and are satisfied when that variable is false. \end{proof} Every simple graph $G$ is $G_\varphi$ for the negative formula with the clause $(\neg x_u\vee\neg x_v)$ for each edge, and in that formula $x_u$ occurs $\deg(u)$ times. Thus Max-Ones for negative 2-CNF formulas is Maximum Independent Set with the same optimum and the same approximation ratio, and negative formulas in which every variable occurs at most $\Delta$ times correspond to graphs of maximum degree at most $\Delta$. For a simple cubic graph $H$ let $N_H$ be the negative formula with $(\neg x_u\vee\neg x_v)$ for every edge $uv$. Every variable of $N_H$ occurs exactly three times, $\operatorname{MaxOnes}(N_H)=\alpha(H)$ by Lemma~\ref{lem:neg-ones}, and Theorem~\ref{thm:identity} reads \[ \operatorname{OPT}(T_H)=4|V|+|E|+\operatorname{MaxOnes}(N_H). \] For a $d$-regular graph $H$ the same holds with $(d+1)|V|+|E|$ in place of $4|V|+|E|$, and for arbitrary simple graphs with $|V|+3|E|$. \subsection{Positive formulas and vertex covers} A \emph{positive} 2-CNF formula $\psi$ has only clauses $(x_u\vee x_v)$ and $(x_u)$; it is not a Horn formula. Let $F$ be the set of variables with a unit clause and $G_\psi$ the graph on the variables outside $F$ with an edge $uv$ for every clause $(x_u\vee x_v)$ with $u,v\notin F$. \begin{lemma}\label{lem:pos-ones} An assignment satisfies $\psi$ if and only if it is true on $F$ and its set of true variables outside $F$ is a vertex cover of $G_\psi$. Hence $\operatorname{MinOnes}(\psi)=|F|+\tau(G_\psi)$, where $\tau$ is the vertex cover number, and $\tau(G_\psi)=|V(G_\psi)|-\alpha(G_\psi)$. \end{lemma} \begin{proof} A unit clause $(x_u)$ is falsified exactly when $x_u$ is false. A clause $(x_u\vee x_v)$ with $u,v\notin F$ is falsified exactly when both are false, so it is satisfied exactly when the true set contains $u$ or $v$. Clauses meeting $F$ are satisfied by the units. The last identity is Gallai's identity for a graph. \end{proof} Every simple graph $G$ is $G_\psi$ for the positive formula with $F=\emptyset$ and the clause $(x_u\vee x_v)$ for each edge; then $\operatorname{MinOnes}(\psi)=\tau(G)$ and $x_u$ occurs $\deg(u)$ times. Min-Ones for positive 2-CNF formulas is therefore Minimum Vertex Cover with the same optimum and the same approximation ratio. Formulas that contain both a positive and a negative literal in some clause, such as the implications $(\neg x\vee y)$ of $T_H$, are not covered by Lemmas~\ref{lem:neg-ones} and~\ref{lem:pos-ones}. \subsection{Hardness of Maximum Independent Set and Vertex Cover} By Lemmas~\ref{lem:neg-ones} and~\ref{lem:pos-ones} and the remarks after them, the following published results apply verbatim to Max-Ones for negative 2-CNF formulas and to Min-Ones for positive 2-CNF formulas, with $N$ the number of variables and $\Delta$ the maximum number of occurrences of a variable. \begin{enumerate} \item Maximum Independent Set is NP-complete~\cite{Karp1972}; it cannot be approximated within $N^{1-\epsilon}$ for any $\epsilon>0$ unless $\mathrm{NP}=\mathrm{ZPP}$~\cite{Hastad1999}, and this holds under $\mathrm{P}\ne\mathrm{NP}$~\cite{Zuckerman2007}. \item Minimum Vertex Cover cannot be approximated within $2-\epsilon$ for any $\epsilon>0$ under the Unique Games Conjecture~\cite{Khot2002,KhotRegev2008}. \item Maximum Independent Set on graphs of maximum degree $\Delta$ cannot be approximated within $\Delta/\log^{2}\Delta$ under the Unique Games Conjecture~\cite{AustrinKhotSafra2011} and within $\Delta/\log^{4}\Delta$ unless $\mathrm{P}=\mathrm{NP}$~\cite{Chan2016}, up to constant factors; it can be approximated within $O(\Delta\log\log\Delta/\log\Delta)$~\cite{Halperin2002}. \item Maximum Independent Set and Minimum Vertex Cover are APX-complete on cubic graphs~\cite{AlimontiKann2000}, so Max-Ones for negative 2-CNF formulas and Min-Ones for positive 2-CNF formulas are APX-complete when every variable occurs exactly three times. \end{enumerate} By Lemma~\ref{lem:neg-ones} the cubic negative formula $N_H$ and the formula $T_H$ of Section~\ref{sec:cubic} have optima that differ by the constant $4|V|+|E|$, and Theorem~\ref{thm:identity} converts an assignment of $T_H$ of value $A$ into a satisfying assignment of $N_H$ with at least $A-(4|V|+|E|)$ true variables. \section{Lean and computational verification} The module \texttt{PalomaMax2SAT.CubicThreeOccurrence} represents the cubic graph with three ports at every vertex. It formalizes the transition count, false edge clauses, explicit deletion repair, independence of the repaired set, its cardinality bound, the matching assignment from an independent set, and the exact optimum identity. It also proves the division-free inequality \[ 84(4n+m+|I|)\ge83(4n+m+\alpha) \] from $2m=3n$, $2\alpha\le n$, and $7|I|\ge6\alpha$, together with the general arithmetic transfer \[ 84\bigl((d+1)n+m+|I|\bigr)\ge83\bigl((d+1)n+m+\alpha\bigr) \] valid for every $d\ge3$ under the analogous hypotheses $2m=dn$ and $2\alpha\le n$. It also proves the rational identity $11+6/7=(83/84)\cdot12$ and the monotonicity statement that the endpoint ratio \((\beta+3/7)/(\beta+1/2)\) is at least \(83/84\) for all \(\beta\ge11/2\). GitHub Actions builds the module and runs the public theorem comparison. The module \texttt{PalomaMax2SAT.SemanticHorn} defines $T_H$ explicitly as a family of clauses, each a list of literals over the clone variables, indexed by the vertices (unit clauses), the edges (edge clauses) and the pairs $(v,i)$ (consistency implications). It proves that the number of clauses of $T_H$ satisfied by $z$ equals $U(z)+(m-F(z))+(4n-T(z))$, that the maximum of this number over all assignments is exactly $4n+m+\alpha$, that every clause has at most one negative literal, that $T_H$ has $5n+m$ clauses, and that every variable occurs exactly three times. The Berman--Fujito guarantee, the Trevisan near-bipartite branch, the Goemans--Williamson rounding, the APX-completeness of cubic Maximum Independent Set, the analytic part of Proposition~\ref{prop:gamma-ratio} and the discussion of the Unique Games Conjecture are proved in the text or taken from the literature and are not formalized in Lean. The module \texttt{PalomaMax2SAT.DegreeTransfer} formalizes the arithmetic of Proposition~\ref{prop:degd}. From $2m=dn$ and $2\alpha\le n$, the value $(d+1)n+m$ satisfies $(3d+2)(B+\alpha)\le(3d+3)B$ with $B=(d+1)n+m$. For $d\ge27$ it satisfies $83(B+\alpha)\le84B$. For $d\ge22$ and $5\alpha\le(d+3)s$ one gets $83(B+\alpha)\le84(B+s)$. From $6\alpha\le7s$ one gets $(21d+20)(B+\alpha)\le(21d+21)(B+s)$, and from $27\alpha\le28s+d\alpha$ one gets $83(B+\alpha)\le84(B+s)$. For $d=21$ it proves the two-branch arithmetic: from $2m=21n$, $2\alpha\le n$, $200\alpha\le99n\Rightarrow50\alpha\le241s$ and $99n<200\alpha\Rightarrow3n\le25s$ one gets $83(22n+m+\alpha)\le84(22n+m+s)$. It also proves the two branches of the $d=21$ argument separately, the inequality $\frac{15803}{241}\cdot\frac{99}{200}<\frac{65}{2}$, the fact that $200\alpha>99n$ gives a cut fraction above $0.99$, the step from at most $7m/100$ uncut edges to $3n\le25|I|$, and the tabulated values of $\rho(d)$ and of $(21d+20)/(21d+21)$. The independent-set guarantees are hypotheses; Lean does not formalize the semidefinite rounding. The module \texttt{PalomaMax2SAT.DegreeFormula} defines $T_H$ for every $d$ as an explicit list of Horn clauses over the $d+1$ clones of each vertex. It proves that the number of satisfied clauses equals $U(z)+(m-F(z))+((d+1)n-T(z))$, that the optimum is exactly $(d+1)n+m+\alpha$, that every clause is Horn, that $T_H$ has $(d+2)n+m$ clauses and that every variable occurs exactly three times. It derives $2m=dn$ from the port structure and $2\alpha\le n$ for $d>0$, proves that the lift of an independent set $I$ has value $(d+1)n+m+|I|$, and combines these with the arithmetic of \texttt{DegreeTransfer} into statements about $T_H$ itself: the baseline ratio $\frac{3d+2}{3d+3}$, the ratio $83/84$ for $d\ge27$, and the transfers of the Berman--Fujito, $6/7$, threshold and $d=21$ hypotheses. The module \texttt{PalomaMax2SAT.GeneralDegreeFormula} proves, for a per-vertex degree function $d_v$ and cycles of length $d_v+1$, the cycle lemma, the repair inequality $\mathrm{val}(z)\le B+|R(z)|$ with $R(z)$ independent, the value $B+|I|$ of the lift of an independent set, and hence the identity $\operatorname{OPT}=B+\alpha$ with $B=\sum_v(d_v+1)+m$, which equals $n+3m$ when $\sum_v d_v=2m$ (Lemma~\ref{lem:general-identity}); it also proves the division-free step $8\alpha\le B$, $18785\,\alpha\le 20000\,|I|\Rightarrow 9932(B+\alpha)\le 10000(B+|I|)$ used in Theorem~\ref{thm:nonreg-cutclass}. The explicit clause list and the three-occurrence count are formalized only for regular graphs, in \texttt{DegreeFormula}. The module \texttt{PalomaMax2SAT.GraphTransfer} formalizes the hard score of the four-port cycle formulation. It proves the exact optima $4m+\alpha$ (edge weight four) and $m+\alpha$ (unit weights), the repair of every feasible assignment, and the division-free transfers $260\,\mathrm{score}\ge257(4m+\alpha)$ and $80\,\mathrm{score}\ge77(m+\alpha)$ from an independent set of size $s$ with $17\alpha\le20s$. The statement $28(m+s)\ge27(m+\alpha)$ is proved from the numerical hypothesis $6\alpha\le7s$, or from $20000\alpha\le9999n$ and $5999993\alpha\le7000000s$; a bridge statement takes the two branch guarantees $20000\alpha\le9999n\Rightarrow5999993\alpha\le7000000s$ and $20000\alpha>9999n\Rightarrow37n\le80s$ as hypotheses. Lean does not prove that an algorithm attains either guarantee. The module \texttt{PalomaMax2SAT.HardOccurrenceSplit} contains the hard-cycle consistency lemma used by this module. The independent Python audit checks 16,314 small Horn formula shapes and verifies equality of the complete sets of attainable source and feasible-split objective values. The repository is available at~\cite{VegaPalomaRepository}. An additional Python audit checks all independent sets on 258 small weighted formulas and enumerates labelled simple subcubic graphs through five vertices for the two-terminal path profile. The general signed-graph theorem and the use of the external approximation algorithms are proved in the text. For every degree $e+2$ it also proves the division-free form of the seventh claim of Proposition~\ref{prop:degd}, with $\varepsilon=1/c$ for a natural number $c$, both as arithmetic and for the lift of an independent set of the formula $T_H$. The arithmetic inequality $63d\le4(d+1)(d+3)+126$ used in the sweep over $d\ge3$ is also proved in \texttt{DegreeTransfer}. The module \texttt{PalomaMax2SAT.CutTransfer} proves Proposition~\ref{prop:cut2sat}(1), that an assignment of $F_G$ satisfies exactly $m+\operatorname{cut}(S)$ clauses, and the arithmetic of the two ratio transfers of Corollary~\ref{cor:cutratio}; the conflict-graph identity of Proposition~\ref{prop:cutconflict} is proved in \texttt{ConflictGraph}. The module \texttt{PalomaMax2SAT.CutLift} proves that an independent set $I$ of $H$ with $18785\,\alpha(H)\le20000\,|I|$ lifts to the ratio $83/84$ on $T_H$ for every degree $D\ge1$, which is the last step of Theorem~\ref{thm:cutclass}; the construction of $I$ from a cut is in \texttt{ConflictGraph} and the cut guarantee is taken from the literature. The module \texttt{PalomaMax2SAT.CitedResults} states the published guarantees used by the $d=21$ argument as explicit hypotheses, namely the existence of a cut with at most $7m/100$ uncut edges~\cite{GoemansWilliamson1995,MahajanRamesh1999} and of a Berman--Fujito independent set~\cite{BermanFujito1999}. It proves that such a cut yields an independent set $I$ with $3n\le25|I|$ and that, under the two hypotheses, some independent set lifts to a $83/84$-approximation of $T_H$ for $d=21$. The module \texttt{PalomaMax2SAT.ConflictGraph} proves $\alpha(H(G))=m+\operatorname{maxcut}(G)$ for every graph given by its edge list, and \texttt{PalomaMax2SAT.ConflictDegree} proves that the conflict graph is $(d+1)$-regular when $G$ is $d$-regular, that $x_v$ occurs $2\deg(v)$ times, that $H(G)$ has $4m$ vertices, and that $M\ge4m$ for every graph (Theorem~\ref{thm:nonreg-cutclass}). The module \texttt{PalomaMax2SAT.LReduction} proves that a graph of maximum degree $\Delta$ has an independent set $I$ with $n\le(\Delta+1)|I|$, the first $L$-reduction constant $\operatorname{OPT}(T_H)\le23\,\alpha(H)$ for cubic graphs and $2\operatorname{OPT}(T_H)\le((3d+2)(d+1)+2)\alpha(H)$ for $d$-regular graphs, and the second constant $1$ (Theorem~\ref{thm:apx}); the APX-completeness of cubic Maximum Independent Set is cited. The module \texttt{PalomaMax2SAT.PaperArithmetic} proves the comparison $\frac{83}{84}>0.94615981>0.94016567$ of Theorem~\ref{thm:ugc-class}, the two-branch arithmetic of Theorem~\ref{thm:ratio} with the two branch guarantees as hypotheses, the numerical constants of Theorems~\ref{thm:cutclass} and~\ref{thm:nonreg-cutclass} and of Proposition~\ref{prop:bounded-cut}, the bound $\gamma/(K+\gamma)\le1/(K+1)$ of Remark~\ref{rem:gamma-linear}, the cube example of Section~\ref{sec:hardfam}, and the tabulated values. The module \texttt{PalomaMax2SAT.SignedGraph} proves Theorem~\ref{thm:signed}: the independent sets of the signed graph are the pairs of a port set and a reward set satisfying the four edge conditions, their weight is at most $DM+\operatorname{OPT}(F)$, an independent set of weight $A$ decodes to an assignment of score at least $A-DM$, and the bound is attained; the vertex count and the maximum degree of the graph are not formalized. The module \texttt{PalomaMax2SAT.OnesBridge} proves, for a cubic port graph $H$ with $\alpha=\alpha(H)$, that $\operatorname{OPT}(T_H)=4|V|+|E|+\alpha$, that $\operatorname{MaxOnes}(N_H)=\alpha$ and that the minimum number of true variables of the positive formula is $|V|-\alpha$. The module \texttt{PalomaMax2SAT.OnesOptimal} proves Lemmas~\ref{lem:neg-ones} and~\ref{lem:pos-ones} and Gallai's identity: an assignment satisfies the negative formula exactly when its true set is an independent set avoiding the unit variables, so the maximum number of true variables is the independence number, and it satisfies the positive formula exactly when the unit variables are true and the remaining true variables cover the remaining edges, so the minimum number of true variables is $|F|$ plus the minimum such cover. The hardness results of Section~\ref{sec:ones} are not formalized. The semidefinite rounding, the Unique Games Conjecture and its hardness thresholds are not formalized; the notes in \texttt{doc/formalization.md} list each cited result with its reference. \begin{thebibliography}{9} \bibitem{AlimontiKann2000} P.~Alimonti and V.~Kann, \emph{Some APX-completeness results for cubic graphs}, Theoretical Computer Science 237 (2000), 123--134. \url{https://doi.org/10.1016/S0304-3975(98)00158-3}. \bibitem{Karp1972} R.~M. Karp, \emph{Reducibility among combinatorial problems}, in Complexity of Computer Computations, Plenum, 1972, 85--103. \bibitem{Hastad1999} J.~H{\aa}stad, \emph{Clique is hard to approximate within $n^{1-\epsilon}$}, Acta Mathematica 182 (1999), 105--142. \bibitem{Zuckerman2007} D.~Zuckerman, \emph{Linear degree extractors and the inapproximability of max clique and chromatic number}, Theory of Computing 3 (2007), 103--128. \bibitem{Khot2002} S.~Khot, \emph{On the power of unique 2-prover 1-round games}, STOC 2002, 767--775. \bibitem{KhotRegev2008} S.~Khot and O.~Regev, \emph{Vertex cover might be hard to approximate to within $2-\epsilon$}, Journal of Computer and System Sciences 74 (2008), 335--349. \bibitem{AustrinKhotSafra2011} P.~Austrin, S.~Khot and M.~Safra, \emph{Inapproximability of vertex cover and independent set in bounded degree graphs}, Theory of Computing 7 (2011), 27--43. \bibitem{Chan2016} S.~O. Chan, \emph{Approximation resistance from pairwise-independent subgroups}, Journal of the ACM 63 (2016), Article 27. \url{https://doi.org/10.1145/2873054}. \bibitem{Halperin2002} E.~Halperin, \emph{Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs}, SIAM Journal on Computing 31 (2002), 1608--1623. \bibitem{Trevisan} L.~Trevisan, \emph{Max Cut and the smallest eigenvalue}, STOC 2009. \url{https://theory.stanford.edu/~trevisan/pubs/maxcutstoc.pdf}. \bibitem{BermanFujito1999} P.~Berman and T.~Fujito, \emph{On approximation properties of the independent set problem for low degree graphs}, Theory of Computing Systems 32 (1999), 115--132. \url{https://doi.org/10.1007/s002240000113}. \bibitem{BrakensiekHuangZwick2024} J.~Brakensiek, N.~Huang, and U.~Zwick, \emph{Tight approximability of MAX 2-SAT and relatives, under UGC}, Proceedings of SODA 2024, 1328--1344. \url{https://doi.org/10.1137/1.9781611977912.53}. \bibitem{FeigeKarpinskiLangberg2002} U.~Feige, M.~Karpinski, and M.~Langberg, \emph{Improved approximation of Max-Cut on graphs of bounded degree}, Journal of Algorithms 43 (2002), 201--219. \bibitem{HalperinLivnatZwick2004} E.~Halperin, D.~Livnat, and U.~Zwick, \emph{MAX CUT in cubic graphs}, Journal of Algorithms 53 (2004), 169--185. \url{https://doi.org/10.1016/j.jalgor.2004.06.001}. \bibitem{HsiehKothari2023} J.-T. Hsieh and P.~K. Kothari, \emph{Approximating Max-Cut on bounded degree graphs: tighter analysis of the FKL algorithm}, ICALP 2023, arXiv:2206.09204. \url{https://arxiv.org/abs/2206.09204}. \bibitem{GHLMM2026} S.~Ghoshal, N.~Huang, E.~Lee, K.~Makarychev, and Y.~Makarychev, \emph{Threshold rounding and bounded-degree Boolean MAX 2-CSP}, arXiv:2607.11050, 2026. \url{https://arxiv.org/abs/2607.11050}. \bibitem{GoemansWilliamson1995} M.~X. Goemans and D.~P. Williamson, \emph{Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming}, Journal of the ACM 42 (1995), 1115--1145. \bibitem{KKMO2007} S.~Khot, G.~Kindler, E.~Mossel, and R.~O'Donnell, \emph{Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?}, SIAM Journal on Computing 37 (2007), 319--357. \bibitem{MahajanRamesh1999} S.~Mahajan and H.~Ramesh, \emph{Derandomizing approximation algorithms based on semidefinite programming}, SIAM Journal on Computing 28 (1999), 1641--1663. \bibitem{OpenAIMath2026} OpenAI, \emph{Proof of Khot's Unique Games Conjecture} (entry~102 of the OpenAI mathematics release, 6~October 2026), GitHub repository \texttt{openai/math}; not peer reviewed. \url{https://github.com/openai/math}. \bibitem{RamanRavikumarRao1998} V.~Raman, B.~Ravikumar, and S.~Srinivasa Rao, \emph{A simplified NP-complete MAXSAT problem}, Information Processing Letters 65 (1998), 1--6. \bibitem{VegaPalomaRepository} F.~Vega, \emph{Paloma: MAX-HORN-2SAT and MAX-CUT formalization}, GitHub, 2026. \url{https://github.com/frankvegadelgado/paloma}. \end{thebibliography} \end{document}