11.3, p. 129 — in a Berge graph with no even prism, rungs and banisters have odd length
ProvedStrongPerfectGraph.OddPrism.banister_rung_oddp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1perfect-graphsstrong-perfect-graph-theorem
Let be a Berge graph containing no even prism, let be a step-connected strip in , and let be a banister with respect to . Then
Odd parity of the rungs and of the banister is used throughout Sections 12 and 13, in particular to see that the banister of a staircase has odd length at least .
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_OddPrism_IsBerge import Definitions.Def_StrongPerfectGraph_OddPrism_IsPrism import Definitions.Def_StrongPerfectGraph_OddPrism_IsStepConnectedStrip import Definitions.Def_StrongPerfectGraph_OddPrism_IsStaircase
Formal statement
namespace StrongPerfectGraph.OddPrism
/-- **11.3** (p. 129). Let `G` be Berge, containing no even prism, let `S = (A, C, B)` be a
step-connected strip in `G`, and let `a₀-R₀-b₀` be a banister. Then every rung of the strip
has odd length, and so does `R₀`. -/
theorem banister_rung_odd {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(hG : IsBerge G) (hprism : ¬ ContainsEvenPrism G)
(A C B : Set V) (hS : IsStepConnected G A C B)
(r₀ : List V) (hr₀ : IsBanister G A C B r₀) :
(∀ r : List V, IsRung G A C B r → Odd (r.length - 1)) ∧ Odd (r₀.length - 1) := by sorry
end StrongPerfectGraph.OddPrism
Source
Chudnovsky, Robertson, Seymour & Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), p. 129, 11.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.