p. 368, proof of THEOREM 2 — if at least one attachment edge is in F, four edges of H suffice
ProvedEdgeDomSets.NPC.H_four_sufficeedge-dominating-setgadgetp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the gadget of Fig. 3. If at least one of the three external edges at is in , then four edges of still suffice: for every nonempty set of corners there is a set of edges of that dominates relative to with
(Fig. 3 shows such in heavy lines for : , , , .)
This gives the upper bound for a satisfiable formula.
Formalization Note is on with the labels of the previous milestone; corners are indexed by Fin 3 ().
Differences from the source:
- encoding: at least one of the three edges at x, y, z is in F → a nonempty set S of corners (Fin 3) whose external edge is in F; reason: same instances
Preamble
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Construction
Formal statement
namespace EdgeDomSets.NPC
theorem H_four_suffice (S : Finset (Fin 3)) (hS : S.Nonempty) :
∃ D : Finset (Sym2 (Fin 14)), EdsRestricted S D ∧ D.card = 4 := by sorry
end EdgeDomSets.NPC
Source
Yannakakis, Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38(3) (1980) 364–372, p. 368, proof of THEOREM 2 (second property of H)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.