Proposition 3.1, p. 157 — a CSUP has a solution in p periods iff its graph Ĝ has a node coloring with p colors
ProvedTimetabling85.CourseColoring.prop_3_1Let be a course scheduling problem with unavailabilities and preassignments (CSUP) in periods: courses with their lectures, students each taking a set of courses, for each course a set of periods at which it cannot take place, and for some lectures a period at which they must take place. Let be the graph constructed in the proof of the proposition: one lecture-node per lecture of course and one period-node per period; two lecture-nodes of one course adjacent; lecture-nodes of distinct courses taken together by some student adjacent; all pairs of period-nodes adjacent; adjacent to period-node if cannot be scheduled at period ; and adjacent to every period-node if has to be scheduled at period . Then
The proposition reduces course scheduling with unavailability and preassignment constraints to plain node colouring, so that any node colouring method applies to the constrained problem.
Formalization Note The paper states the proposition as "one can construct a graph such that …". Read literally as an existential over graphs it would be trivially true (take a complete graph on nodes or an edgeless graph according to the answer), so the statement is made about the specific graph of the proof, csupGraph P, defined in the definitions file. Periods are Fin p; is allowed, and then both sides hold exactly when there are no lectures.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_Timetabling85_CourseColoring_CSUP
namespace Timetabling85.CourseColoring
theorem prop_3_1 {q r p : ℕ} (P : CSUP q r p) :
(∃ s : P.Lecture → Fin p, P.IsFeasible s) ↔ P.csupGraph.Colorable p := by sorry
end Timetabling85.CourseColoring
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.