p. 367, proof of THEOREM 2 — G has maximum degree 4 (corrected: the degree-4 nodes are d_j / d'_j of one-sign 3-literal clauses)
ProvedEdgeDomSets.NPC.G_degreedegreeedge-dominating-setp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a SAT-3-restricted formula and its graph. Every vertex of has degree at most 4, and a vertex has degree 4 if and only if
These are the vertices that the substitution of the gadget removes, so that has maximum degree 3.
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 , . "Degree at least 4" is written as the negation of DegreeLE (G φ) w 3.
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 - correction: the degree-4 nodes are the d_i's where C_i is a 3-literal clause → the degree-4 nodes are d_j for C_j with three positive literals and d'_j for C_j with three negated literals; reason: d_j has degree 1 + (positive literals of C_j) and d'_j 1 + (negated ones); counterexample: C1 = (x1 ∨ x2 ∨ x̄1), C2 = (x1 ∨ x2), C3 = (x̄2) is SAT-3-restricted, C1 has 3 literals but deg d_1 = 3, deg d'_1 = 2; for C = (x̄1 ∨ x̄2 ∨ x̄3) the node d' has degree 4
- reading: maximum degree 4 → every vertex has degree ≤ 4, with equality exactly at the listed nodes; reason: "maximum degree 4" is attained only when a one-sign 3-literal clause exists; the iff gives the attained case
- 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)
Preamble
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Construction
Formal statement
namespace EdgeDomSets.NPC
theorem G_degree (φ : CookLevin.Formula) (hφ : IsSat3Restricted φ) :
MaxDegreeLE (G φ) 4 ∧
∀ w : GV φ, ¬ DegreeLE (G φ) w 3 ↔
∃ j : Fin φ.length, (φ.get j).length = 3 ∧
((w = dNode j ∧ ∀ l ∈ φ.get j, ∃ v, l = CookLevin.Literal.Pos v) ∨
(w = dNode' j ∧ ∀ l ∈ φ.get j, ∃ v, l = CookLevin.Literal.Neg v)) := by sorry
end EdgeDomSets.NPC
Source
Yannakakis, Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38(3) (1980) 364–372, p. 367, proof of THEOREM 2, last paragraph ("The graph G constructed above has maximum degree 4.")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.