Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.1, p. 157 — a CSUP has a solution in p periods iff its graph Ĝ has a node coloring with p colors

Proved
Timetabling85.CourseColoring.prop_3_1

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

course-schedulinggraph-coloringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reductiontimetabling

Let PPP be a course scheduling problem with unavailabilities and preassignments (CSUP) in ppp periods: courses KbK_bKb​ 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 G^\hat GG^ be the graph constructed in the proof of the proposition: one lecture-node mabm_{ab}mab​ per lecture lal_ala​ of course KbK_bKb​ 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; mabm_{ab}mab​ adjacent to period-node kkk if KbK_bKb​ cannot be scheduled at period kkk; and mabm_{ab}mab​ adjacent to every period-node k≠kˉk \ne \bar kk=kˉ if lal_ala​ has to be scheduled at period kˉ\bar kkˉ. Then

P has a solution in p periods  ⟺  G^ has a node coloring with p colors.P \text{ has a solution in } p \text{ periods} \iff \hat G \text{ has a node coloring with } p \text{ colors}.P has a solution in p periods⟺G^ has a node coloring with p colors.

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 G^\hat GG^ such that …". Read literally as an existential over graphs it would be trivially true (take a complete graph on p+1p+1p+1 nodes or an edgeless graph according to the answer), so the statement is made about the specific graph G^\hat GG^ of the proof, csupGraph P, defined in the definitions file. Periods are Fin p; p=0p = 0p=0 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.

Preamble
import Mathlib
import Definitions.Def_Timetabling85_CourseColoring_CSUP
Formal statement
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
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 157, Proposition 3.1, with the graph Ĝ of its proof, pp. 157–158
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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