/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import Mathlib.Combinatorics.SimpleGraph.Clique
public import Mathlib.Combinatorics.SimpleGraph.CycleGraph
public import Mathlib.Tactic.AbelChordal graphs and clique edge partitions
Definitions and basic results used in Erdős Problem 81.
@[expose] public sectionnamespace SimpleGraphvariable {V : Type*}
A graph is chordal if it contains no induced cycle of length k ≥ 4.
def IsChordal (G : SimpleGraph V) : Prop :=
∀ k : ℕ, 4 ≤ k → ¬ (cycleGraph k).IsIndContained G
P is a partition of the edges of G into cliques: each member of P is a clique
of G with at least two vertices, and every edge of G is contained in exactly one
member of P.
def IsCliqueEdgePartition (G : SimpleGraph V) (P : Finset (Finset V)) : Prop :=
(∀ s ∈ P, 2 ≤ s.card ∧ G.IsClique (s : Set V)) ∧
∀ u v : V, G.Adj u v → ∃! s, s ∈ P ∧ u ∈ s ∧ v ∈ sA graph is a split graph if its vertex set splits into a clique and an independent set.
def IsSplitGraph (G : SimpleGraph V) : Prop :=
∃ S : Set V, G.IsClique S ∧ G.IsIndepSet SᶜEvery finite graph has a clique edge partition consisting of its edges.
refine_3.h V:Type u_2inst✝²:Fintype Vinst✝¹:DecidableEq VG:SimpleGraph Vinst✝:DecidableRel G.Adje':Sym2 Va✝:e' ∈ ↑G.edgeFinseta:Vb:Vh:s(a, b).toFinset = e'.toFinsethe:s(a, b) ∈ G.edgeSethab:G.Adj a bha:a ∈ e'hb:b ∈ e'⊢ s(a, b) = e'
exact ((Sym2.mem_and_mem_iff hab.ne).mp ⟨ha, hb⟩).symm All goals completed! 🐙private lemma cycleGraph_adj_succ (m : ℕ) (a : Fin (m + 4)) : (cycleGraph (m + 4)).Adj a (a + 1) :=
(cycleGraph_adj (n := m + 2)).mpr (Or.inr (by m:ℕa:Fin (m + 4)⊢ a + 1 - a = 1 simp All goals completed! 🐙))
private lemma cycleGraph_not_adj_add_two (m : ℕ) (a : Fin (m + 4)) :
a ≠ a + 1 + 1 ∧ ¬ (cycleGraph (m + 4)).Adj a (a + 1 + 1) := by m:ℕa:Fin (m + 4)⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)
have key : (1 + 1 : Fin (m + 4)) ≠ 1 ∧ (1 + 1 : Fin (m + 4)) ≠ 0 ∧
(-(1 + 1) : Fin (m + 4)) ≠ 1 := by
refine ⟨?_, ?_, ?_⟩ refine_1 m:ℕa:Fin (m + 4)⊢ 1 + 1 ≠ 1refine_2 m:ℕa:Fin (m + 4)⊢ 1 + 1 ≠ 0refine_3 m:ℕa:Fin (m + 4)⊢ -(1 + 1) ≠ 1 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) <;> refine_1 m:ℕa:Fin (m + 4)⊢ 1 + 1 ≠ 1refine_2 m:ℕa:Fin (m + 4)⊢ 1 + 1 ≠ 0refine_3 m:ℕa:Fin (m + 4)⊢ -(1 + 1) ≠ 1 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) intro h refine_3 m:ℕa:Fin (m + 4)h:-(1 + 1) = 1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) <;> refine_1 m:ℕa:Fin (m + 4)h:1 + 1 = 1⊢ Falserefine_2 m:ℕa:Fin (m + 4)h:1 + 1 = 0⊢ Falserefine_3 m:ℕa:Fin (m + 4)h:-(1 + 1) = 1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) rw [Fin.ext_iff refine_1 m:ℕa:Fin (m + 4)h:↑(1 + 1) = ↑1⊢ False refine_3 m:ℕa:Fin (m + 4)h:↑(-(1 + 1)) = ↑1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)] refine_2 m:ℕa:Fin (m + 4)h:↑(1 + 1) = ↑0⊢ Falserefine_3 m:ℕa:Fin (m + 4)h:↑(-(1 + 1)) = ↑1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) at hrefine_3 m:ℕa:Fin (m + 4)h:↑(-(1 + 1)) = ↑1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)
· refine_1 m:ℕa:Fin (m + 4)h:↑(1 + 1) = ↑1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) simp [Fin.val_add, Nat.mod_eq_of_lt] at h All goals completed! 🐙 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)
· refine_2 m:ℕa:Fin (m + 4)h:↑(1 + 1) = ↑0⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) simp [Fin.val_add, Nat.mod_eq_of_lt] at h All goals completed! 🐙 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)
· refine_3 m:ℕa:Fin (m + 4)h:↑(-(1 + 1)) = ↑1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) rw [Fin.val_neg' refine_3 m:ℕa:Fin (m + 4)h:(m + 4 - ↑(1 + 1)) % (m + 4) = ↑1⊢ False refine_3 m:ℕa:Fin (m + 4)h:(m + 4 - ↑(1 + 1)) % (m + 4) = ↑1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)] at hrefine_3 m:ℕa:Fin (m + 4)h:(m + 4 - ↑(1 + 1)) % (m + 4) = ↑1⊢ False m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)
simp [Fin.val_add, Nat.mod_eq_of_lt] at h m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1) m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1⊢ a ≠ a + 1 + 1 ∧ ¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)
refine ⟨fun h => ?_, fun h => ?_⟩ refine_1 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:a = a + 1 + 1⊢ Falserefine_2 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:(cycleGraph (m + 4)).Adj a (a + 1 + 1)⊢ False
· refine_1 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:a = a + 1 + 1⊢ False have := congrArg (fun x => x - a) h refine_1 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:a = a + 1 + 1this:a - a = a + 1 + 1 - a⊢ False
simp only [sub_self] at this refine_1 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:a = a + 1 + 1this:0 = a + 1 + 1 - a⊢ False
exact key.2.1 (by m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:a = a + 1 + 1this:0 = a + 1 + 1 - a⊢ 1 + 1 = 0 rw [this m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:a = a + 1 + 1this:0 = a + 1 + 1 - a⊢ 1 + 1 = a + 1 + 1 - a m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:a = a + 1 + 1this:0 = a + 1 + 1 - a⊢ 1 + 1 = a + 1 + 1 - a] m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:a = a + 1 + 1this:0 = a + 1 + 1 - a⊢ 1 + 1 = a + 1 + 1 - a; abel All goals completed! 🐙)
· refine_2 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h:(cycleGraph (m + 4)).Adj a (a + 1 + 1)⊢ False rcases (cycleGraph_adj (n := m + 2)).mp h with h | h refine_2.inl m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a - (a + 1 + 1) = 1⊢ Falserefine_2.inr m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a + 1 + 1 - a = 1⊢ False
· refine_2.inl m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a - (a + 1 + 1) = 1⊢ False exact key.2.2 (by m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a - (a + 1 + 1) = 1⊢ -(1 + 1) = 1 rw [show -(1 + 1 : Fin (m + 4)) = a - (a + 1 + 1) by m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a - (a + 1 + 1) = 1⊢ -(1 + 1) = 1 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a - (a + 1 + 1) = 1⊢ a - (a + 1 + 1) = 1 abel All goals completed! 🐙 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a - (a + 1 + 1) = 1⊢ a - (a + 1 + 1) = 1] m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a - (a + 1 + 1) = 1⊢ a - (a + 1 + 1) = 1; exact h All goals completed! 🐙)
· refine_2.inr m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a + 1 + 1 - a = 1⊢ False exact key.1 (by m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a + 1 + 1 - a = 1⊢ 1 + 1 = 1 rw [show (1 + 1 : Fin (m + 4)) = a + 1 + 1 - a by m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a + 1 + 1 - a = 1⊢ 1 + 1 = 1 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a + 1 + 1 - a = 1⊢ a + 1 + 1 - a = 1 abel All goals completed! 🐙 m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a + 1 + 1 - a = 1⊢ a + 1 + 1 - a = 1] m:ℕa:Fin (m + 4)key:1 + 1 ≠ 1 ∧ 1 + 1 ≠ 0 ∧ -(1 + 1) ≠ 1h✝:(cycleGraph (m + 4)).Adj a (a + 1 + 1)h:a + 1 + 1 - a = 1⊢ a + 1 + 1 - a = 1; exact h All goals completed! 🐙)Every split graph is chordal.
theorem IsSplitGraph.isChordal {V : Type*} {G : SimpleGraph V} (hG : G.IsSplitGraph) :
G.IsChordal := by V:Type u_2G:SimpleGraph VhG:G.IsSplitGraph⊢ G.IsChordal
obtain ⟨S, hS, hI⟩ := hG V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜ⊢ G.IsChordal
intro k hk ⟨f⟩ V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜk:ℕhk:4 ≤ kf:cycleGraph k ↪g G⊢ False
obtain ⟨m, rfl⟩ := Nat.exists_eq_add_of_le' hk V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g G⊢ False
have noK : ∀ a, f a ∈ S → f (a + 1 + 1) ∈ S → False := fun a ha hb => by
obtain ⟨hne, hna⟩ := cycleGraph_not_adj_add_two m a V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g Ga:Fin (m + 4)ha:f a ∈ Shb:f (a + 1 + 1) ∈ Shne:a ≠ a + 1 + 1hna:¬(cycleGraph (m + 4)).Adj a (a + 1 + 1)⊢ False V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → False⊢ False
exact hna (f.map_adj_iff.mp (hS ha hb (f.injective.ne hne))) V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → False⊢ False V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → False⊢ False
have noI : ∀ a, f a ∉ S → f (a + 1) ∉ S → False := fun a ha hb => by
have h := f.map_adj_iff.mpr (cycleGraph_adj_succ m a) V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → Falsea:Fin (m + 4)ha:f a ∉ Shb:f (a + 1) ∉ Sh:G.Adj (f a) (f (a + 1))⊢ False V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → False⊢ False
exact hI ha hb h.ne h V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → False⊢ False V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → False⊢ False
by_cases h1 : f (0 + 1) ∈ S pos V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∈ S⊢ Falseneg V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∉ S⊢ False
· pos V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∈ S⊢ False have h3 : f (0 + 1 + 1 + 1) ∉ S := fun h => noK _ h1 h pos V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∈ Sh3:f (0 + 1 + 1 + 1) ∉ S⊢ False
have h2 : f (0 + 1 + 1) ∈ S := by_contra fun h => noI _ h h3 pos V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∈ Sh3:f (0 + 1 + 1 + 1) ∉ Sh2:f (0 + 1 + 1) ∈ S⊢ False
have h4 : f (0 + 1 + 1 + 1 + 1) ∈ S := by_contra fun h => noI _ h3 h pos V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∈ Sh3:f (0 + 1 + 1 + 1) ∉ Sh2:f (0 + 1 + 1) ∈ Sh4:f (0 + 1 + 1 + 1 + 1) ∈ S⊢ False
exact noK _ h2 h4 All goals completed! 🐙
· neg V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∉ S⊢ False have h0 : f 0 ∈ S := by_contra fun h => noI _ h h1 neg V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∉ Sh0:f 0 ∈ S⊢ False
have h2 : f (0 + 1 + 1) ∈ S := by_contra fun h => noI _ h1 h neg V:Type u_2G:SimpleGraph VS:Set VhS:G.IsClique ShI:G.IsIndepSet Sᶜm:ℕhk:4 ≤ m + 4f:cycleGraph (m + 4) ↪g GnoK:∀ (a : Fin (m + 4)), f a ∈ S → f (a + 1 + 1) ∈ S → FalsenoI:∀ (a : Fin (m + 4)), f a ∉ S → f (a + 1) ∉ S → Falseh1:f (0 + 1) ∉ Sh0:f 0 ∈ Sh2:f (0 + 1 + 1) ∈ S⊢ False
exact noK _ h0 h2 All goals completed! 🐙The empty family partitions the edges of an edgeless graph.
@[simp] theorem isCliqueEdgePartition_bot_empty :
(⊥ : SimpleGraph V).IsCliqueEdgePartition ∅ := by V:Type u_1⊢ ⊥.IsCliqueEdgePartition ∅
simp [IsCliqueEdgePartition] All goals completed! 🐙An edgeless graph is split, including when its vertex type is empty.
theorem isSplitGraph_bot : (⊥ : SimpleGraph V).IsSplitGraph := by V:Type u_1⊢ ⊥.IsSplitGraph
exact ⟨∅, by V:Type u_1⊢ ⊥.IsClique ∅ simp All goals completed! 🐙, by V:Type u_1⊢ ⊥.IsIndepSet ∅ᶜ simp [IsIndepSet, Set.Pairwise] All goals completed! 🐙⟩end SimpleGraph