7.1, p. 92 — three internally disjoint tracks through prescribed edges in a 3-connected graph
ProvedStrongPerfectGraph.LineGraph.three_tracksgraph-theoryp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be adjacent vertices of a -connected graph , and let and be two distinct edges of incident with and different from . Then there are three tracks of from to , pairwise vertex-disjoint except for their ends, whose first edges are , and respectively.
The lemma is used to build prisms around a branch of an appearance in the rung-replacement argument of §7.
Formalization Note The track with first edge is the edge itself; the other two are and with disjoint interiors. The page writes "edges "; they are taken distinct, as the conclusion (three tracks pairwise disjoint except for their ends) requires.
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_LineGraph_IsSubdivision
Formal statement
namespace StrongPerfectGraph.LineGraph
theorem three_tracks {W : Type*} [Fintype W] (J : SimpleGraph W) (hJ : IsThreeConnected J)
(c₁ c₂ x y : W) (h₁₂ : J.Adj c₁ c₂) (hx : J.Adj c₁ x) (hy : J.Adj c₁ y)
(hx₂ : x ≠ c₂) (hy₂ : y ≠ c₂) (hxy : x ≠ y) :
IsTrack J [c₁, c₂] ∧
∃ q r : List W, IsTrack J (c₁ :: x :: q ++ [c₂]) ∧ IsTrack J (c₁ :: y :: r ++ [c₂]) ∧
∀ z ∈ x :: q, z ∉ y :: r := by sorry
end StrongPerfectGraph.LineGraph
Source
Chudnovsky, Robertson, Seymour & Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), p. 92, 7.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.