Proof of Proposition 2.4, p. 155 — a timetable exists iff the conflict graph has n pairwise non-adjacent nodes
ProvedTimetabling85.TwoPeriod.timetable_iff_stableLet be an instance of the daily class–teacher problem CT4 with classes, teachers and periods, and let be its conflict graph: one node for each pair (teacher , possible schedule of ), two nodes linked when they are different schedules of the same teacher or when they put the same class in the same period. Then
This is the reduction on which de Werra's algorithm for Proposition 2.4 rests: in the two-period case it turns the timetabling question into the question of finding a stable set with one node from each pair .
Formalization Note The statement holds for every CT4 instance, without the two-period bound; the page's "graph with nodes" is the case in which every teacher has exactly two schedules, while in general has nodes. "Set of pairwise non-adjacent nodes" is Mathlib's IsNIndepSet n.
import Mathlib import Definitions.Def_Timetabling85_TwoPeriod_CT4
namespace Timetabling85.TwoPeriod
theorem timetable_iff_stable {m n p : ℕ} (I : CT4Data m n p) :
(∃ x : Fin m → Fin n → Fin p → Bool, IsSolution I x) ↔
∃ S : Finset (Node I), (conflictGraph I).IsNIndepSet n S := by sorry
end Timetabling85.TwoPeriod
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.