p. 368, proof of THEOREM 2 — H − {x, y, z} is three u–v paths of length 4, so H needs at least four of its own edges
ProvedEdgeDomSets.NPC.H_four_needededge-dominating-setgadgetp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the gadget of Fig. 3. Then
- consists of three – paths of length 4 (internally vertex-disjoint, covering all its vertices and edges);
- therefore needs at least four edges for its domination: even if all three external edges at are in , must contain four more edges of . In the Lean form, for every set of corners whose external edge is in and every set of edges of dominating relative to ,
Together with the next two properties this fixes the cost of each gadget in the threshold .
Formalization Note is on with , , , , , . The three paths are a map with , . Corners are indexed by Fin 3 ().
Differences from the source:
- encoding: H as drawn in Fig. 3; "even if all three edges incident to x, y, z are in F" → H on Fin 14 with fixed labels; for every set S of corners whose external edge is in F; reason: S = {x, y, z} is the weakest hypothesis, so the statement for every S is equivalent to the printed one
Preamble
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Construction
Formal statement
namespace EdgeDomSets.NPC
theorem H_four_needed :
(∃ P : Fin 3 → Fin 5 → Fin 14,
(∀ i, P i 0 = hu ∧ P i 4 = hv) ∧
(∀ i (k : Fin 4), H.Adj (P i k.castSucc) (P i k.succ)) ∧
(∀ i k, P i k ≠ hx ∧ P i k ≠ hy ∧ P i k ≠ hz) ∧
(∀ i i' (k k' : Fin 5), 0 < k → k < 4 → P i k = P i' k' → i = i' ∧ k = k') ∧
(∀ w, w ≠ hx → w ≠ hy → w ≠ hz → ∃ i k, P i k = w) ∧
(∀ a b, a ≠ hx → a ≠ hy → a ≠ hz → b ≠ hx → b ≠ hy → b ≠ hz → H.Adj a b →
∃ (i : Fin 3) (k : Fin 4), s(a, b) = s(P i k.castSucc, P i k.succ))) ∧
∀ (S : Finset (Fin 3)) (D : Finset (Sym2 (Fin 14))), EdsRestricted S D → 4 ≤ 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 (first property of H)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.