/- 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.Abel

Chordal 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 ∈ s

A 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.

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' 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 (m:ℕa:Fin (m + 4)⊢ a + 1 - a = 1 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; All goals completed! 🐙)

Every split graph is chordal.

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 → Falseh1:f (0 + 1) ∈ S⊢ FalseV: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 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 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 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 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 All goals completed! 🐙 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 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 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 All goals completed! 🐙

The empty family partitions the edges of an edgeless graph.

@[simp] theorem isCliqueEdgePartition_bot_empty : (⊥ : SimpleGraph V).IsCliqueEdgePartition ∅ := V:Type u_1⊢ ⊥.IsCliqueEdgePartition ∅ All goals completed! 🐙

An edgeless graph is split, including when its vertex type is empty.

theorem isSplitGraph_bot : (⊥ : SimpleGraph V).IsSplitGraph := V:Type u_1⊢ ⊥.IsSplitGraph exact ⟨∅, V:Type u_1⊢ ⊥.IsClique ∅ All goals completed! 🐙, V:Type u_1⊢ ⊥.IsIndepSet ∅ᶜ All goals completed! 🐙⟩end SimpleGraph