Proof of Proposition 2.4, pp. 154–155 — a teacher available in at most 2 periods has at most 2 possible schedules
ProvedTimetabling85.TwoPeriod.card_schedules_le_twoConsider an instance of the daily class–teacher problem CT4 with classes, teachers and periods, and fix a teacher . Call a array a possible schedule of if for every class , at most classes meet at each period , and meets at period only if . If teacher is available during at most periods, i.e. , then
This is the step of the proof of Proposition 2.4 that gives every teacher at most two nodes in the conflict graph.
Formalization Note The page says each teacher has exactly possible schedules, after the normalisation "one may clearly assume that all teachers are available for 2 periods exactly". Without that normalisation the number can be , or (for example one lecture of a single class and two free periods gives two schedules, two lectures of the same class gives one), so the faithful content is the bound .
import Mathlib import Definitions.Def_Timetabling85_TwoPeriod_CT4
namespace Timetabling85.TwoPeriod
theorem card_schedules_le_two {m n p : ℕ} (I : CT4Data m n p) (j : Fin n)
(hj : (Finset.univ.filter fun k => I.cbar j k = true).card ≤ 2) :
(schedules I j).card ≤ 2 := by sorry
end Timetabling85.TwoPeriod
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.