p. 368, proof of THEOREM 2 — if no attachment edge is in F, F needs at least five edges of H
ProvedEdgeDomSets.NPC.H_five_needededge-dominating-setgadgetp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the gadget of Fig. 3. If none of the three external edges at belongs to , then must contain at least five edges of : every set of edges of that dominates all edges of satisfies
This is what forces a literal edge into every gadget when the edge dominating set has the threshold size, i.e. what makes a small edge dominating set of satisfy the replaced clauses.
Formalization Note is on with the labels of the first gadget milestone; "dominates relative to " is plain domination of by edges of .
Differences from the source:
- encoding: none of the three edges at x, y, z belongs to F → EdsRestricted ∅ D; reason: same instances
Preamble
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Construction
Formal statement
namespace EdgeDomSets.NPC
theorem H_five_needed (D : Finset (Sym2 (Fin 14))) (hD : EdsRestricted ∅ D) :
5 ≤ D.card := 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 (third property of H)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.