Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

THEOREM 2, p. 367 — the edge dominating set problem for bipartite graphs of maximum degree 3 is NP-complete

Proved
EdgeDomSets.NPC.theorem_2

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

edge-dominating-setnp-completenessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Assume that the SAT-3-restricted problem is NP-complete (the paper takes this from its reference [13]). Then the edge dominating set problem for bipartite graphs with maximum degree 3 — given a graph GGG that is bipartite with all degrees at most 3 and a positive integer kkk, does GGG have a set of at most kkk edges which dominate all the other edges? — is NP-complete:

SAT3R NP-complete ⟹ EDSbip,3 NP-complete.\mathrm{SAT3R}\ \text{NP-complete}\ \Longrightarrow\ \mathrm{EDS}_{\mathrm{bip},3}\ \text{NP-complete}.SAT3R NP-complete ⟹ EDSbip,3​ NP-complete.

NP-completeness means membership in NP together with NP-hardness under polynomial-time many-one reductions. The result shows that minimum maximal matching is NP-hard even on bipartite graphs of maximum degree 3, and is the input to the paper's COROLLARY 1 on independent sets of total graphs.

Formalization Note NP-completeness is CookLevin.NPComplete (multi-tape Turing machines, polynomial step bounds). Graphs are coded by the published NPGraph encoding, formulas by the CookLevin formula code.

Differences from the source:

  • reading: "The reduction is from the SAT-3-restricted problem" (NP-complete by [13]) → hypothesis CookLevin.NPComplete sat3rLang; reason: the paper cites [13] (Yannakakis 1978) for it; it is not on the platform and is not part of this paper
  • reading: bipartite graphs with maximum degree 3; a positive integer k → simple graph with Colorable 2, every degree ≤ 3, and 1 ≤ k; reason: paper.md reading 6; "maximum degree 3" as an upper bound
  • encoding: NP-complete (Cook [2], Karp [9]) → CookLevin.NPComplete on binary codes (NPGraph graph code, CookLevin formula code); reason: the published framework of the Proved 3-SAT and CLIQUE results
  • generalization: the SAT-3 restricted problem (a set of clauses, at most three literals per clause, every variable two times and its negation once) → sat3rLang: codes of satisfiable formulas with IsSat3Restricted, occurrences counted with multiplicity (repeated literals or clauses, a clause with x and x̄, empty clauses allowed); reason: sat3rLang contains every instance of the printed problem; the printed problem reduces to it by sending its instances to themselves and everything else to a fixed no-instance, so NP-completeness of the printed problem gives that of sat3rLang, and a reduction from sat3rLang gives one from the printed problem (paper.md reading 4)
Preamble
import Mathlib
import Definitions.Def_EdgeDomSets_NPC_Problems
Formal statement
namespace EdgeDomSets.NPC

theorem theorem_2 (h : CookLevin.NPComplete sat3rLang) :
    CookLevin.NPComplete edsBip3Lang := by sorry

end EdgeDomSets.NPC
Source
Yannakakis, Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38(3) (1980) 364–372, p. 367, THEOREM 2
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me