simple_graph_triangle_free_pair_stable_nonbipartite_example
A triangle-free two-edge-stable graph can fail to be bipartite; its empty packing is maximum and support-maximal.
Statement
theorem simple_graph_triangle_free_pair_stable_nonbipartite_example : ∃ G : SimpleGraph (Fin 5), G.CliqueFree 3 ∧
(∀ e f : Sym2 (Fin 5), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f →
simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧
(∀ f : Fin 5 → Bool, ∃ u v, G.Adj u v ∧ f u = f v)- Source
- A five-cycle refutes the unrestricted unpacked-edge bipartiteness shortcut; compare experiment 20873.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_triangle_packing_number_monoTriangle packing number is monotone under subgraph inclusion: if H ≤ G, then ν(H) ≤ ν(G).
- simple_graph_triangle_packing_number_eq_zero_of_clique_freeA triangle-free graph has triangle packing number 0.
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
The proof, explained
The 5-cycle graph C_5 is triangle-free, has no 2-coloring, and has triangle packing number zero. Since deleting any two edges leaves a subgraph, its packing number remains zero, establishing pair-stability.
G has symmetric adjacency
The adjacency relation is symmetric because unordered pairs in E are symmetric.
uses
Sym2.eq_swapsymm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩
G contains no triangles automation
By finite exhaustion of all 3-element subsets of Fin 5, none is a 3-clique.
uses
Finset.mem_powersetCard.mpr,Finset.subset_univtheorem no_triangle : G.CliqueFree 3 := by have h : ∀ t ∈ (Finset.univ : Finset (Fin 5)).powersetCard 3, ¬ G.IsNClique 3 t := by decide +kernel intro t ht exact h t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _,ht.card_eq⟩) ht
- Unresolved check: no step explains line(s) 15, 22, 23, 24, 25, 32 -- every tactic of the proof has to belong to some step
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped Sym2namespace In701Odddef E : Finset (Sym2 (Fin 5)) := {s(0,1),s(1,2),s(2,3),s(3,4),s(4,0)}def G : SimpleGraph (Fin 5) where Adj u v := s(u,v) ∈ E ∧ u ≠ v symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩ loopless := ⟨fun u h => h.2 rfl⟩instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ∈ E ∧ _ ≠ _))theorem no_triangle : G.CliqueFree 3 := by have h : ∀ t ∈ (Finset.univ : Finset (Fin 5)).powersetCard 3, ¬ G.IsNClique 3 t := by decide +kernel intro t ht exact h t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _,ht.card_eq⟩) httheorem no_coloring : ∀ f : Fin 5 → Bool, ∃ u v, G.Adj u v ∧ f u = f v := by decide +kerneltheorem packing_zero : simple_graph_triangle_packing_number G = 0 := simple_graph_triangle_packing_number_eq_zero_of_clique_free G no_triangletheorem stable : ∀ e f : Sym2 (Fin 5), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G := by intro e f _ _ _ have h := simple_graph_triangle_packing_number_mono G (G.deleteEdges {e,f}) (SimpleGraph.deleteEdges_le _) rw [packing_zero] at h ⊢ omegaend In701Oddtheorem simple_graph_triangle_free_pair_stable_nonbipartite_example : ∃ G : SimpleGraph (Fin 5), G.CliqueFree 3 ∧ (∀ e f : Sym2 (Fin 5), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧ (∀ f : Fin 5 → Bool, ∃ u v, G.Adj u v ∧ f u = f v) := by exact ⟨In701Odd.G,In701Odd.no_triangle,In701Odd.stable,In701Odd.no_coloring⟩