9.1, p. 108 — knots in Berge graphs have odd paths and antipaths, two of length one
ProvedStrongPerfectGraph.DoubleSplit.knot_odd_lengthsdouble-split-graphp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1perfect-graphsstrong-perfect-graph-theorem
Let be a knot in a Berge graph . Then all have odd length, and
where is the length (number of edges) of a path or antipath.
Consequently a knot in a Berge graph is a degenerate appearance of in or in .
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsBerge import Definitions.Def_StrongPerfectGraph_DoubleSplit_IsKnot
Formal statement
namespace StrongPerfectGraph.DoubleSplit
/-- 9.1 (p. 108): in a knot `(P₁, P₂, Q₁, Q₂)` of a Berge graph all four paths and antipaths have
odd length, and either `P₁, P₂` both have length one or `Q₁, Q₂` both have length one. The length
of a list is its number of vertices minus one. -/
theorem knot_odd_lengths {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(hG : StrongPerfectGraph.Main.IsBerge G) (P₁ P₂ Q₁ Q₂ : List V) (hK : IsKnot G P₁ P₂ Q₁ Q₂) :
(Odd (P₁.length - 1) ∧ Odd (P₂.length - 1) ∧ Odd (Q₁.length - 1) ∧ Odd (Q₂.length - 1)) ∧
((P₁.length - 1 = 1 ∧ P₂.length - 1 = 1) ∨ (Q₁.length - 1 = 1 ∧ Q₂.length - 1 = 1)) := by sorry
end StrongPerfectGraph.DoubleSplit
Source
Chudnovsky, Robertson, Seymour & Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), p. 108, 9.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.