The Wonderful Lemma of Roussel and Rubio
ProvedStrongPerfectGraph.Wonderful.roussel_rubioberge-graphsgraph-theoryperfect-graphsstrong-perfect-graph-theorem
The Wonderful Lemma (Roussel–Rubio). Let be a Berge graph (no odd hole and no odd antihole), let be anticonnected (the complement graph induced on is connected), and let be an induced path of odd length in whose ends are both complete to . Then at least one of the following holds:
- some edge of is -complete (both ends adjacent to every vertex of );
- and contains a leap for : nonadjacent with and ;
- and there is an odd antipath from to with interior in .
In the formalization is a list-based induced path with an even number of vertices, and the antipath is an induced path of the complement graph.
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsBerge import Definitions.Def_StrongPerfectGraph_Main_IsInducedPath
Formal statement
namespace StrongPerfectGraph.Wonderful
open StrongPerfectGraph.Main
/-- **The Wonderful Lemma** (Roussel and Rubio; Theorem 1.2 of Chudnovsky's short proof, Theorem 2.1 of
Chudnovsky–Robertson–Seymour–Thomas). Let `G` be Berge, `X` an anticonnected set of vertices, and
`P = v₀ … v_k` an induced path with `k` odd (an even number of vertices), disjoint from `X`, whose two
ends are complete to `X`. Then (1) two consecutive vertices of `P` are both complete to `X`, or
(2) `k ≥ 5` and `X` contains a leap for `P` (nonadjacent `a, b ∈ X` with `N(a) ∩ P = {v₀, v₁, v_k}` and
`N(b) ∩ P = {v₀, v_{k-1}, v_k}`), or (3) `k = 3` and there is an odd antipath from `v₁` to `v₂` with
interior in `X`. -/
theorem roussel_rubio {V : Type*} {G : SimpleGraph V} (hG : IsBerge G) {X : Finset V}
(hX : (Gᶜ.induce (X : Set V)).Connected) {P : List V} (hP : IsInducedPath G P)
(hlen : Even P.length) (hdisj : ∀ v ∈ P, v ∉ X) {v0 vk : V} (h0 : P.head? = some v0)
(hk : P.getLast? = some vk) (hv0 : ∀ x ∈ X, G.Adj v0 x) (hvk : ∀ x ∈ X, G.Adj vk x) :
(∃ (i : ℕ) (u w : V), P[i]? = some u ∧ P[i + 1]? = some w ∧ (∀ x ∈ X, G.Adj u x) ∧
(∀ x ∈ X, G.Adj w x)) ∨
(6 ≤ P.length ∧ ∃ a ∈ X, ∃ b ∈ X, a ≠ b ∧ ¬ G.Adj a b ∧
(∀ (i : ℕ) (v : V), P[i]? = some v →
(G.Adj a v ↔ (i = 0 ∨ i = 1 ∨ i + 1 = P.length))) ∧
(∀ (i : ℕ) (v : V), P[i]? = some v →
(G.Adj b v ↔ (i = 0 ∨ i + 2 = P.length ∨ i + 1 = P.length)))) ∨
(P.length = 4 ∧ ∃ Q : List V, IsInducedPath Gᶜ Q ∧ Even Q.length ∧
(∃ v1 v2, P[1]? = some v1 ∧ P[2]? = some v2 ∧ Q.head? = some v1 ∧
Q.getLast? = some v2) ∧
∀ (i : ℕ) (v : V), Q[i]? = some v → 0 < i → i + 1 < Q.length → v ∈ X) := by sorry
end StrongPerfectGraph.Wonderful
Source
M. Chudnovsky, A short proof of the Wonderful Lemma (2017), Theorem 1.2; M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), Theorem 2.1 (due to Roussel and Rubio).