Remark, p. 155 — in a graph with a perfect matching a stable set has at most |X|/2 nodes, one end of each matching edge
ProvedTimetabling85.TwoPeriod.remark_perfect_matchinggraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1perfect-matchingstable-set
Let be a finite graph with a perfect matching . Then
- every stable set of satisfies ;
- every stable set with contains exactly one endpoint of every edge of : for each edge ,
These two facts are what make de Werra's Remark work: identifying the edges of with the pairs of the proof of Proposition 2.4, a stable set of nodes is exactly a choice of one node per pair with no conflicts, so the limited backtracking decides whether such a set exists.
Formalization Note The Remark's algorithmic claim (an algorithm) is not formalized; the statement records the combinatorial content that transports the procedure from graphs on to any graph with a perfect matching. is natural-number division, exact here because a perfect matching makes even.
Preamble
import Mathlib
Formal statement
namespace Timetabling85.TwoPeriod
theorem remark_perfect_matching {X : Type*} [Fintype X] [DecidableEq X]
(G : SimpleGraph X) (M : G.Subgraph) (hM : M.IsPerfectMatching) :
(∀ S : Finset X, G.IsIndepSet (S : Set X) → S.card ≤ Fintype.card X / 2) ∧
(∀ S : Finset X, G.IsIndepSet (S : Set X) → S.card = Fintype.card X / 2 →
∀ v w : X, M.Adj v w → (v ∈ S ↔ w ∉ S)) := by sorry
end Timetabling85.TwoPeriod
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 155, Remark after the proof of Proposition 2.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.