8.1, p. 99 — all uv-rungs of a strip system have the same parity
ProvedStrongPerfectGraph.LineGraph.rung_paritygraph-theoryline-graphsp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1perfect-graphs
Let be a -strip system in a Berge graph , where is -connected. Then for every edge of , all -rungs have lengths of the same parity:
Hence any choice of one rung per edge of induces the line graph of a bipartite subdivision of .
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsBerge import Definitions.Def_StrongPerfectGraph_LineGraph_IsSubdivision import Definitions.Def_StrongPerfectGraph_LineGraph_IsStripSystem
Formal statement
namespace StrongPerfectGraph.LineGraph
theorem rung_parity {V W : Type*} [Fintype V] [Fintype W]
(G : SimpleGraph V) (hG : StrongPerfectGraph.Main.IsBerge G) (J : SimpleGraph W) (hJ : IsThreeConnected J)
(S : W → W → Set V) (N : W → Set V) (hSN : IsStripSystem J G S N) :
∀ u v : W, J.Adj u v → ∀ R R' : List V, IsRung G S N u v R → IsRung G S N u v R' →
(R.length - 1) % 2 = (R'.length - 1) % 2 := by sorry
end StrongPerfectGraph.LineGraph
Source
Chudnovsky, Robertson, Seymour & Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), p. 99, 8.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.