p. 367, proof of THEOREM 2 — the bipartition (S, T) of the graph G
ProvedEdgeDomSets.NPC.G_bipartitionLet be a SAT-3-restricted formula and the graph of the proof of THEOREM 2. The printed partition
is a bipartition of : every edge of joins a vertex of to a vertex of . In particular is bipartite.
This is the first step towards the bipartiteness of the graph produced by the reduction.
Formalization Note Clause and position indices are 0-based (Fin). The vertices of are indexed by literal occurrences: the occurrence has a literal vertex lit o (the paper's , or ), a pendant pend o (the primed copy) and a variable-side vertex varNode o ( or for the two positive occurrences of , for the negated one); dNode j, dNode' j are , . The side of a vertex is the Boolean inS (true for ).
Differences from the source:
- encoding: vertices a_i, b_i, c_i, (a_i, j1), (b_i, j2), (c_i, j3), their primed copies, d_j, d'_j, with 1-based indices → one literal vertex, one pendant vertex and one variable-side vertex per literal occurrence (clause index, position), plus d_j, d'_j, all 0-based (
Fin); reason: under SAT-3-restricted the three occurrences of x_i are exactly x_i ∈ C_j1, x_i ∈ C_j2, x̄_i ∈ C_j3, so the vertices and edges are the printed ones - generalization: a set of clauses with at most three literals per clause, every variable occurring two times and its negation once → IsSat3Restricted φ on a list of literal lists: occurrences counted with multiplicity, so a clause may repeat a literal or hold x and x̄, clauses may repeat, and empty clauses are allowed; reason: every instance of the printed problem satisfies IsSat3Restricted, so the statement specializes to the source's claim on each of them; the construction and the argument are unchanged on the extra formulas (paper.md reading 4)
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Construction
namespace EdgeDomSets.NPC
theorem G_bipartition (φ : CookLevin.Formula) (hφ : IsSat3Restricted φ) :
(∀ a b : GV φ, (G φ).Adj a b → inS a ≠ inS b) ∧ (G φ).Colorable 2 := by sorry
end EdgeDomSets.NPC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.