Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Proposition 3.1, p. 158 — lecture l_a of K_b is at period k iff m_ab has the color of period-node k; colorings of Ĝ ↔ feasible schedules

Proved
Timetabling85.CourseColoring.coloring_interpretation

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

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

Let PPP be a course scheduling problem with unavailabilities and preassignments (CSUP) in ppp periods, and let G^\hat GG^ be its graph: lecture-nodes mabm_{ab}mab​, period-nodes 1,…,p1,\dots,p1,…,p, the edges of the lecture graph, all pairs of period-nodes, mabm_{ab}mab​ joined to kkk when course KbK_bKb​ cannot be held at period kkk, and mabm_{ab}mab​ joined to every k≠kˉk \ne \bar kk=kˉ when lal_ala​ has to be held at period kˉ\bar kkˉ.

  1. For every node colouring ccc of G^\hat GG^ with ppp colours there is a solution sss of PPP in ppp periods with
s(la of Kb)=k  ⟺  c(mab)=c(k)for every lecture and every period k.s(l_a \text{ of } K_b) = k \iff c(m_{ab}) = c(k) \qquad \text{for every lecture and every period } k.s(la​ of Kb​)=k⟺c(mab​)=c(k)for every lecture and every period k.
  1. Conversely, for every solution sss of PPP in ppp periods there is a node colouring ccc of G^\hat GG^ with ppp colours related to sss in the same way.

This is the interpretation of the coloured graph G^\hat GG^ given in the proof of Proposition 3.1: the schedule is read off a colouring through the colours of the period-nodes.

Formalization Note The colouring's palette is Fin p, but the statement does not require period-node kkk to receive colour kkk: a colouring may permute the colours of the period clique, and the schedule is read through the colour of each period-node.

Preamble
import Mathlib
import Definitions.Def_Timetabling85_CourseColoring_CSUP
Formal statement
namespace Timetabling85.CourseColoring

theorem coloring_interpretation {q r p : ℕ} (P : CSUP q r p) :
    (∀ c : P.csupGraph.Coloring (Fin p), ∃ s : P.Lecture → Fin p, P.IsFeasible s ∧
      ∀ (l : P.Lecture) (k : Fin p), s l = k ↔ c (Sum.inl l) = c (Sum.inr k)) ∧
    (∀ s : P.Lecture → Fin p, P.IsFeasible s → ∃ c : P.csupGraph.Coloring (Fin p),
      ∀ (l : P.Lecture) (k : Fin p), s l = k ↔ c (Sum.inl l) = c (Sum.inr k)) := by sorry

end Timetabling85.CourseColoring
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 158, proof of Proposition 3.1, "The interpretation of the colored graph Ĝ is the following: …"
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