AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_free_pair_stable_nonbipartite_example

theoremverified

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

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.

  1. G has symmetric adjacency

    The adjacency relation is symmetric because unordered pairs in E are symmetric.

    line 7

    uses Sym2.eq_swap

      symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩
  2. G contains no triangles automation

    By finite exhaustion of all 3-element subsets of Fin 5, none is a 3-clique.

    lines 11–14

    uses Finset.mem_powersetCard.mpr, Finset.subset_univ

    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⟩) ht

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

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⟩
See it in the graphDiscuss this resultChallenge it