AFTD Auto-Formalizing Theoretical Domains

simple_graph_pair_stable_triangle_active_incidence_two_unpacked_nonbipartite

theoremverified

There is a triangle-active two-edge-stable eight-vertex graph with a support-maximal maximum triangle packing in which every vertex is in at most two packed triangles, while the graph of unpacked edges is not bipartite.

Statement

theorem simple_graph_pair_stable_triangle_active_incidence_two_unpacked_nonbipartite : ∃ (G : SimpleGraph (Fin 8)) (P : Finset (Finset (Fin 8))),
    (∀ t ∈ P, G.IsNClique 3 t) ∧
    (P : Set (Finset (Fin 8))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧
    P.card = simple_graph_triangle_packing_number G ∧ P.biUnion id = Finset.univ ∧
    (∀ v : Fin 8, (P.filter (fun t => v ∈ t)).card ≤ 2) ∧
    (∀ e f : Sym2 (Fin 8), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f →
       simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧
    (∀ e : Sym2 (Fin 8), e ∈ G.edgeSet → ∃ t : Finset (Fin 8), G.IsNClique 3 t ∧ e ∈ finite_vertex_set_edge_encoding t) ∧
    (∀ f : Fin 8 → Bool, ∃ u v : Fin 8, G.Adj u v ∧
      s(u,v) ∉ P.biUnion finite_vertex_set_edge_encoding ∧ f u = f v)
Source
The explicit finite counterexample in state/campaigns/triangle_reductions/incidence_two_nonbipartite_cert_in701.json refutes an unpacked-edge bipartiteness shortcut, even when every edge belongs to a triangle.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof explicitly constructs an 8-vertex graph G with 19 edges and a triangle packing P of 4 edge-disjoint triangles. Exhaustive kernel computation verifies that G has exactly 20 triangles and that no packing can exceed size 4, making P a maximum triangle packing. Two-edge stability is proved using a precomputed list of 17 witness packings, ensuring that for any pair of deleted edges, at least one 4-triangle packing survives intact. Finally, kernel verification confirms that P covers all vertices, touches each vertex at most twice, and leaves a non-bipartite graph of unpacked edges.

  1. The graph G is well-defined on Fin 8 with 19 edges, having a symmetric and loopless adjacency relation.

    The graph G is defined with edge set given by the 19 pairs in EL. Symmetry of adjacency follows from the symmetry of unordered pairs (Sym2.eq_swap), and looplessness holds by requiring distinct endpoints.

    lines 6–14

    uses Sym2.eq_swap

    def EL : List (Sym2 (Fin 8)) := [s(0,2), s(0,4), s(0,6), s(0,7), s(1,3), s(1,5), s(1,6), s(1,7), s(2,4), s(2,6), s(2,7), s(3,5), s(3,6), s(3,7), s(4,6), s(4,7), s(5,6), s(5,7), s(6,7)]
    def T : List (Finset (Fin 8)) := [{0,2,4}, {0,2,6}, {0,2,7}, {0,4,6}, {0,4,7}, {0,6,7}, {1,3,5}, {1,3,6}, {1,3,7}, {1,5,6}, {1,5,7}, {1,6,7}, {2,4,6}, {2,4,7}, {2,6,7}, {3,5,6}, {3,5,7}, {3,6,7}, {4,6,7}, {5,6,7}]
    def P : Finset (Finset (Fin 8)) := {{0,2,4}, {0,6,7}, {1,3,6}, {3,5,7}}
    def E : Finset (Sym2 (Fin 8)) := EL.toFinset
    def G : SimpleGraph (Fin 8) 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 ∧ _ ≠ _))
  2. The 3-cliques of G are precisely the 20 triples listed in T. automation

    Kernel evaluation checks every 3-element subset of Fin 8, establishing that every 3-clique in G belongs to T (tri_complete) and every triple in T induces a 3-clique in G (T_clique).

    lines 16–20

    theorem tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 8)).powersetCard 3,
        G.IsNClique 3 t → t ∈ T := by decide +kernel
    theorem T_clique : ∀ t ∈ T, G.IsNClique 3 t := by decide +kernel
    lemma clique_mem {t : Finset (Fin 8)} (h : G.IsNClique 3 t) : t ∈ T :=
      tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) h
  3. Any collection of pairwise edge-disjoint triangles in G has cardinality at most 4.

    Two triangles are edge-disjoint if and only if their intersection has at most one vertex. Kernel evaluation confirms that the maximum clique in this compatibility graph of T has size 4 (maxC_eq). By in693_maxC_bound, any pairwise compatible family of triangles in G has size at most 4 (nu_le).

    lines 21–29

    uses in693_maxC_bound, maxC_eq

    def compat (s t : Finset (Fin 8)) : Bool := decide ((s ∩ t).card ≤ 1)
    theorem maxC_eq : in693_maxC compat T.length T = 4 := by decide +kernel
    lemma nu_le (U : Finset (Finset (Fin 8))) (hU : ∀ t ∈ U, G.IsNClique 3 t)
        (hP : (U : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : U.card ≤ 4 :=
      calc U.card ≤ in693_maxC compat T.length T :=
            in693_maxC_bound compat _ T le_rfl U (fun a ha => clique_mem (hU a ha))
              (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab))
        _ = 4 := maxC_eq
    
  4. The triangle packing number of G is 4, attained by the packing P.

    Kernel evaluation verifies that the 4 triangles in P are valid 3-cliques (P_clique) and pairwise edge-disjoint (P_pw). Since |P| = 4 (P_card) and every packing has size at most 4 (nu_le), 4 is the maximum packing number (IsGreatest.csSup_eq).

    lines 30–38

    uses IsGreatest.csSup_eq, nu_le, P_clique, P_pw, P_card

    theorem P_clique : ∀ t ∈ P, G.IsNClique 3 t := by decide +kernel
    theorem P_pw : (P : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kernel
    theorem P_card : P.card = 4 := by decide +kernel
    theorem pack_eq : simple_graph_triangle_packing_number G = 4 := by
      unfold simple_graph_triangle_packing_number
      refine IsGreatest.csSup_eq ⟨⟨P, P_clique, P_pw, P_card⟩, ?_⟩
      rintro n ⟨U, h1, h2, rfl⟩
      exact nu_le U h1 h2
    
  5. The family of triangle edge sets of G is the image under edge encoding of the triangles in T.

    By extensionality, a set of edges forms a triangle in G if and only if it is the encoding of some triple in T, using clique_mem and T_clique to relate 3-cliques to T.

    lines 39–49

    uses clique_mem, T_clique

    theorem family : simple_graph_triangle_edge_family G =
        T.toFinset.image finite_vertex_set_edge_encoding := by
      classical
      ext x
      simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset]
      constructor
      · rintro ⟨t, ht, rfl⟩
        exact ⟨t, clique_mem ht, rfl⟩
      · rintro ⟨t, ht, rfl⟩
        exact ⟨t, T_clique t ht, rfl⟩
    
  6. The packing P covers all 8 vertices, every vertex belongs to at most two triangles in P, and the unpacked edges form a non-bipartite graph. automation

    Kernel computation checks three finite statements: the union of triangles in P is the entire vertex set Fin 8 (P_support); filtering P for triangles containing any given vertex yields at most 2 triangles (P_mult); and for every 2-coloring f : Fin 8 → Bool, there exists an edge of G not in any packed triangle whose endpoints share the same color (P_nonbip).

    lines 50–54

    theorem P_support : P.biUnion id = Finset.univ := by decide +kernel
    theorem P_mult : ∀ v : Fin 8, (P.filter (fun t => v ∈ t)).card ≤ 2 := by decide +kernel
    theorem P_nonbip : ∀ f : Fin 8 → Bool, ∃ u v : Fin 8,
        G.Adj u v ∧ s(u,v) ∉ P.biUnion finite_vertex_set_edge_encoding ∧ f u = f v := by decide +kernel
    
  7. Every edge in EL belongs to at least one triangle in T. automation

    Kernel evaluation exhaustively verifies that each of the 19 edges in EL is contained in at least one triangle from the list T (T_active).

    lines 55–56

    theorem T_active : ∀ e ∈ EL, ∃ t ∈ T, e ∈ finite_vertex_set_edge_encoding t := by decide +kernel
    
  8. Every pair of edges in G is avoided by a packing of 4 edge-disjoint triangles provided by a witness list W. automation

    A list W of 17 pairs (edge_list, packing) is defined. Kernel evaluation checks that every pair of edges e, f ∈ EL is contained in the edge list of some witness q ∈ W (W_cover), and that for each witness q, the 4 triangles in q.2 are pairwise edge-disjoint triangles in T avoiding all edges in q.1 (W_ok).

    lines 57–83

    def W : List (List (Sym2 (Fin 8)) × List (Finset (Fin 8))) := [
      ([s(0,2), s(0,4), s(1,3), s(1,6), s(2,6), s(3,7), s(4,6)], [{0,6,7}, {1,5,7}, {2,4,7}, {3,5,6}]),
      ([s(0,2), s(0,6), s(2,7), s(3,5), s(3,6), s(5,7), s(6,7)], [{0,4,7}, {1,3,7}, {1,5,6}, {2,4,6}]),
      ([s(0,2), s(0,7), s(1,5), s(1,7), s(2,4), s(4,7), s(5,6)], [{0,4,6}, {1,3,6}, {2,6,7}, {3,5,7}]),
      ([s(0,4), s(0,6), s(1,3), s(1,5), s(3,6), s(4,7), s(5,6)], [{0,2,7}, {1,6,7}, {2,4,6}, {3,5,7}]),
      ([s(1,5), s(1,6), s(2,4), s(2,6), s(4,7), s(5,7), s(6,7)], [{0,2,7}, {0,4,6}, {1,3,7}, {3,5,6}]),
      ([s(0,4), s(0,7), s(1,3), s(1,7), s(3,5), s(4,6), s(5,7)], [{0,2,6}, {1,5,6}, {2,4,7}, {3,6,7}]),
      ([s(2,4), s(2,7), s(3,5), s(3,7), s(4,6), s(5,6), s(6,7)], [{0,2,6}, {0,4,7}, {1,3,6}, {1,5,7}]),
      ([s(0,6), s(0,7), s(1,3), s(1,7), s(2,6), s(2,7), s(3,6)], [{0,2,4}, {1,5,6}, {3,5,7}, {4,6,7}]),
      ([s(1,5), s(1,6), s(2,4), s(2,7), s(3,5), s(3,6), s(4,6)], [{0,2,6}, {0,4,7}, {1,3,7}, {5,6,7}]),
      ([s(0,6), s(0,7), s(1,3), s(1,6), s(3,7), s(4,6), s(4,7)], [{0,2,4}, {1,5,7}, {2,6,7}, {3,5,6}]),
      ([s(1,3), s(1,6), s(2,4), s(2,6), s(3,5), s(4,7), s(5,6)], [{0,2,7}, {0,4,6}, {1,5,7}, {3,6,7}]),
      ([s(0,4), s(0,7), s(1,3), s(1,7), s(3,6), s(4,6), s(6,7)], [{0,2,6}, {1,5,6}, {2,4,7}, {3,5,7}]),
      ([s(0,2), s(0,6), s(1,6), s(1,7), s(2,7), s(3,6), s(3,7)], [{0,4,7}, {1,3,5}, {2,4,6}, {5,6,7}]),
      ([s(0,2), s(0,4), s(1,3), s(1,6), s(2,7), s(3,7), s(4,7)], [{0,6,7}, {1,5,7}, {2,4,6}, {3,5,6}]),
      ([s(0,2), s(0,6), s(1,3), s(1,5), s(2,7), s(3,7), s(5,7)], [{0,4,7}, {1,6,7}, {2,4,6}, {3,5,6}]),
      ([s(0,4), s(0,6), s(1,3), s(1,6), s(2,4), s(2,6), s(3,7)], [{0,2,7}, {1,5,7}, {3,5,6}, {4,6,7}]),
      ([s(0,2), s(0,6), s(1,6), s(1,7), s(2,7), s(5,6), s(5,7)], [{0,4,7}, {1,3,5}, {2,4,6}, {3,6,7}])
    ]
    theorem W_cover : ∀ e ∈ EL, ∀ f ∈ EL,
        ∃ q ∈ W, e ∈ q.1 ∧ f ∈ q.1 := by decide +kernel
    
    theorem W_ok : ∀ q ∈ W, q.2.toFinset.card = 4 ∧
        (∀ t ∈ q.2, t ∈ T) ∧
        (∀ a ∈ q.2, ∀ b ∈ q.2, a ≠ b → (a ∩ b).card ≤ 1) ∧
        (∀ e ∈ q.1, ∀ t ∈ q.2, e ∉ t.sym2) := by decide +kernel
    
  9. The graph G is triangle-active: every edge of G belongs to a triangle.

    Every edge of G belongs to the list EL (edge_mem, proved using Sym2.ind and SimpleGraph.mem_edgeSet). Combining this with T_active and T_clique shows that every edge belongs to a 3-clique in G.

    lines 84–95

    uses Sym2.ind, SimpleGraph.mem_edgeSet, T_active, edge_mem, T_clique

    lemma edge_mem {g : Sym2 (Fin 8)} (h : g ∈ G.edgeSet) : g ∈ EL := by
      induction g using Sym2.ind with
      | _ a b =>
        have h1 := ((SimpleGraph.mem_edgeSet G).mp h).1
        exact List.mem_toFinset.mp h1
    
    theorem active : ∀ e : Sym2 (Fin 8), e ∈ G.edgeSet →
        ∃ t : Finset (Fin 8), G.IsNClique 3 t ∧ e ∈ finite_vertex_set_edge_encoding t := by
      intro e he
      obtain ⟨t,ht,het⟩ := T_active e (edge_mem he)
      exact ⟨t,T_clique t ht,het⟩
    
  10. A triangle in G disjoint from edges e and f remains a 3-clique in G \setminus {e, f}.

    For any two distinct vertices in the triangle, the edge connecting them cannot be e or f, because neither edge has both endpoints in the triangle. Thus all edges of the triangle survive edge deletion (SimpleGraph.deleteEdges_adj).

    lines 96–113

    uses SimpleGraph.deleteEdges_adj

    lemma del_clique {t : Finset (Fin 8)} {e f : Sym2 (Fin 8)}
        (h : G.IsNClique 3 t) (he : ¬ ∀ x ∈ e, x ∈ t) (hf : ¬ ∀ x ∈ f, x ∈ t) :
        (G.deleteEdges {e,f}).IsNClique 3 t := by
      refine ⟨?_, h.card_eq⟩
      intro a ha b hb hab
      refine (SimpleGraph.deleteEdges_adj).mpr ⟨h.isClique ha hb hab, ?_⟩
      intro hmem
      simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hmem
      rcases hmem with hmem | hmem
      · apply he
        rw [← hmem]
        intro x hx
        rcases Sym2.mem_iff.mp hx with rfl | rfl <;> assumption
      · apply hf
        rw [← hmem]
        intro x hx
        rcases Sym2.mem_iff.mp hx with rfl | rfl <;> assumption
    
  11. The graph G is two-edge-stable: deleting any two distinct edges leaves the triangle packing number at 4.

    For any distinct edges e and f, W_cover provides a witness whose 4 triangles avoid both edges; by del_clique and W_ok, these 4 triangles survive in G \setminus {e, f}, giving a packing of size 4. Since G \setminus {e, f} is a subgraph of G (SimpleGraph.deleteEdges_le), any packing in the subgraph is also a packing in G, so its size cannot exceed 4 by nu_le. Therefore the packing number remains 4 (IsGreatest.csSup_eq).

    lines 114–133

    uses pack_eq, W_cover, edge_mem, W_ok, IsGreatest.csSup_eq, del_clique, T_clique, nu_le, SimpleGraph.deleteEdges_le

    theorem stable : ∀ e f : Sym2 (Fin 8), 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 he hf hne
      rw [pack_eq]
      obtain ⟨q, hq, hqe, hqf⟩ := W_cover e (edge_mem he) f (edge_mem hf)
      obtain ⟨hc, ht, hp, hav⟩ := W_ok q hq
      unfold simple_graph_triangle_packing_number
      refine IsGreatest.csSup_eq ⟨⟨q.2.toFinset, ?_, ?_, hc⟩, ?_⟩
      · intro t ht'
        have ht'' := List.mem_toFinset.mp ht'
        apply del_clique (T_clique t (ht t ht''))
        · intro h; exact hav e hqe t ht'' (Finset.mem_sym2_iff.mpr h)
        · intro h; exact hav f hqf t ht'' (Finset.mem_sym2_iff.mpr h)
      · intro a ha b hb hab
        exact hp a (List.mem_toFinset.mp (Finset.mem_coe.mp ha))
          b (List.mem_toFinset.mp (Finset.mem_coe.mp hb)) hab
      · rintro k ⟨U, hU, hP, rfl⟩
        exact nu_le U (fun t ht' => (hU t ht').mono (SimpleGraph.deleteEdges_le _)) hP
    end In701Free
  12. There exists an 8-vertex graph and a triangle packing satisfying all required conditions.

    The existential statement is witnessed by G and P. All required properties are discharged by the previously established theorems (In701Free.P_clique, In701Free.P_pw, In701Free.P_support, In701Free.P_mult, In701Free.stable, In701Free.active, In701Free.P_nonbip), and the packing cardinality condition |P| = nu(G) is resolved by rewriting with In701Free.P_card and In701Free.pack_eq.

    lines 135–146

    uses In701Free.P_clique, In701Free.P_pw, In701Free.P_support, In701Free.P_mult, In701Free.stable, In701Free.active, In701Free.P_nonbip, In701Free.P_card, In701Free.pack_eq

    theorem simple_graph_pair_stable_triangle_active_incidence_two_unpacked_nonbipartite : ∃ (G : SimpleGraph (Fin 8)) (P : Finset (Finset (Fin 8))),
        (∀ t ∈ P, G.IsNClique 3 t) ∧
        (P : Set (Finset (Fin 8))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧
        P.card = simple_graph_triangle_packing_number G ∧ P.biUnion id = Finset.univ ∧
        (∀ v : Fin 8, (P.filter (fun t => v ∈ t)).card ≤ 2) ∧
        (∀ e f : Sym2 (Fin 8), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f →
           simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧
        (∀ e : Sym2 (Fin 8), e ∈ G.edgeSet → ∃ t : Finset (Fin 8), G.IsNClique 3 t ∧ e ∈ finite_vertex_set_edge_encoding t) ∧
        (∀ f : Fin 8 → Bool, ∃ u v : Fin 8, G.Adj u v ∧
          s(u,v) ∉ P.biUnion finite_vertex_set_edge_encoding ∧ f u = f v) := by
      refine ⟨In701Free.G,In701Free.P,In701Free.P_clique,In701Free.P_pw,?_,In701Free.P_support,In701Free.P_mult,In701Free.stable,In701Free.active,In701Free.P_nonbip⟩
      rw [In701Free.P_card,In701Free.pack_eq]
Sym2.eq_swap
An unordered pair s(a, b) is identical to s(b, a).
in693_maxC_bound
Any pairwise compatible subset of a list of length at most n has size bounded by in693_maxC c n l.
maxC_eq
The computed maximum clique bound on the triangle compatibility graph is 4.
IsGreatest.csSup_eq
The supremum of a set is its maximum whenever that maximum is attained in the set.
P_clique
Every triangle in P is a 3-clique in G.
P_pw
The triangles in P are pairwise edge-disjoint.
P_card
The packing P contains exactly 4 triangles.
nu_le
Any family of pairwise edge-disjoint triangles in G has cardinality at most 4.
clique_mem
Every 3-clique in G belongs to the list of 20 triangles T.
T_clique
Every triangle in the list T is a 3-clique in G.
Sym2.ind
Proof principle stating that any property of an unordered pair holds if it holds for all representations s(x, y).
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) is in the edge set of a simple graph if and only if v and w are adjacent.
T_active
Every edge in EL is contained in at least one triangle in T.
edge_mem
Every edge of the graph G belongs to the edge list EL.
SimpleGraph.deleteEdges_adj
An edge is present in G \setminus s if and only if it is present in G and does not belong to s.
pack_eq
The maximum triangle packing number of G is 4.
W_cover
Every pair of edges in EL is contained in the edge set of at least one witness in W.
W_ok
Every witness in W contains 4 pairwise edge-disjoint triangles from T that are disjoint from the witness edge set.
del_clique
A triangle in G remains a triangle in G \setminus {e, f} if neither e nor f has both endpoints in the triangle.
SimpleGraph.deleteEdges_le
Deleting edges from a graph produces a subgraph (G \setminus s \le G).
In701Free.P_clique
Every triangle in P is a 3-clique in G.
In701Free.P_pw
The triangles in P are pairwise edge-disjoint.
In701Free.P_card
The candidate packing P contains exactly 4 triangles.
In701Free.pack_eq
The triangle packing number of G is 4.
In701Free.P_support
The union of all triangles in P covers all 8 vertices.
In701Free.P_mult
Every vertex belongs to at most two triangles of P.
In701Free.stable
Deleting any two distinct edges from G preserves its triangle packing number.
In701Free.active
Every edge of G belongs to at least one triangle in G.
In701Free.P_nonbip
For any 2-coloring of the vertices, there is an unpacked edge whose endpoints have the same color.

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 Sym2set_option maxRecDepth 100000set_option maxHeartbeats 30000000namespace In701Freedef EL : List (Sym2 (Fin 8)) := [s(0,2), s(0,4), s(0,6), s(0,7), s(1,3), s(1,5), s(1,6), s(1,7), s(2,4), s(2,6), s(2,7), s(3,5), s(3,6), s(3,7), s(4,6), s(4,7), s(5,6), s(5,7), s(6,7)]def T : List (Finset (Fin 8)) := [{0,2,4}, {0,2,6}, {0,2,7}, {0,4,6}, {0,4,7}, {0,6,7}, {1,3,5}, {1,3,6}, {1,3,7}, {1,5,6}, {1,5,7}, {1,6,7}, {2,4,6}, {2,4,7}, {2,6,7}, {3,5,6}, {3,5,7}, {3,6,7}, {4,6,7}, {5,6,7}]def P : Finset (Finset (Fin 8)) := {{0,2,4}, {0,6,7}, {1,3,6}, {3,5,7}}def E : Finset (Sym2 (Fin 8)) := EL.toFinsetdef G : SimpleGraph (Fin 8) 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 tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 8)).powersetCard 3,    G.IsNClique 3 t → t ∈ T := by decide +kerneltheorem T_clique : ∀ t ∈ T, G.IsNClique 3 t := by decide +kernellemma clique_mem {t : Finset (Fin 8)} (h : G.IsNClique 3 t) : t ∈ T :=  tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) hdef compat (s t : Finset (Fin 8)) : Bool := decide ((s ∩ t).card ≤ 1)theorem maxC_eq : in693_maxC compat T.length T = 4 := by decide +kernellemma nu_le (U : Finset (Finset (Fin 8))) (hU : ∀ t ∈ U, G.IsNClique 3 t)    (hP : (U : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : U.card ≤ 4 :=  calc U.card ≤ in693_maxC compat T.length T :=        in693_maxC_bound compat _ T le_rfl U (fun a ha => clique_mem (hU a ha))          (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab))    _ = 4 := maxC_eqtheorem P_clique : ∀ t ∈ P, G.IsNClique 3 t := by decide +kerneltheorem P_pw : (P : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kerneltheorem P_card : P.card = 4 := by decide +kerneltheorem pack_eq : simple_graph_triangle_packing_number G = 4 := by  unfold simple_graph_triangle_packing_number  refine IsGreatest.csSup_eq ⟨⟨P, P_clique, P_pw, P_card⟩, ?_⟩  rintro n ⟨U, h1, h2, rfl⟩  exact nu_le U h1 h2theorem family : simple_graph_triangle_edge_family G =    T.toFinset.image finite_vertex_set_edge_encoding := by  classical  ext x  simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset]  constructor  · rintro ⟨t, ht, rfl⟩    exact ⟨t, clique_mem ht, rfl⟩  · rintro ⟨t, ht, rfl⟩    exact ⟨t, T_clique t ht, rfl⟩theorem P_support : P.biUnion id = Finset.univ := by decide +kerneltheorem P_mult : ∀ v : Fin 8, (P.filter (fun t => v ∈ t)).card ≤ 2 := by decide +kerneltheorem P_nonbip : ∀ f : Fin 8 → Bool, ∃ u v : Fin 8,    G.Adj u v ∧ s(u,v) ∉ P.biUnion finite_vertex_set_edge_encoding ∧ f u = f v := by decide +kerneltheorem T_active : ∀ e ∈ EL, ∃ t ∈ T, e ∈ finite_vertex_set_edge_encoding t := by decide +kerneldef W : List (List (Sym2 (Fin 8)) × List (Finset (Fin 8))) := [  ([s(0,2), s(0,4), s(1,3), s(1,6), s(2,6), s(3,7), s(4,6)], [{0,6,7}, {1,5,7}, {2,4,7}, {3,5,6}]),  ([s(0,2), s(0,6), s(2,7), s(3,5), s(3,6), s(5,7), s(6,7)], [{0,4,7}, {1,3,7}, {1,5,6}, {2,4,6}]),  ([s(0,2), s(0,7), s(1,5), s(1,7), s(2,4), s(4,7), s(5,6)], [{0,4,6}, {1,3,6}, {2,6,7}, {3,5,7}]),  ([s(0,4), s(0,6), s(1,3), s(1,5), s(3,6), s(4,7), s(5,6)], [{0,2,7}, {1,6,7}, {2,4,6}, {3,5,7}]),  ([s(1,5), s(1,6), s(2,4), s(2,6), s(4,7), s(5,7), s(6,7)], [{0,2,7}, {0,4,6}, {1,3,7}, {3,5,6}]),  ([s(0,4), s(0,7), s(1,3), s(1,7), s(3,5), s(4,6), s(5,7)], [{0,2,6}, {1,5,6}, {2,4,7}, {3,6,7}]),  ([s(2,4), s(2,7), s(3,5), s(3,7), s(4,6), s(5,6), s(6,7)], [{0,2,6}, {0,4,7}, {1,3,6}, {1,5,7}]),  ([s(0,6), s(0,7), s(1,3), s(1,7), s(2,6), s(2,7), s(3,6)], [{0,2,4}, {1,5,6}, {3,5,7}, {4,6,7}]),  ([s(1,5), s(1,6), s(2,4), s(2,7), s(3,5), s(3,6), s(4,6)], [{0,2,6}, {0,4,7}, {1,3,7}, {5,6,7}]),  ([s(0,6), s(0,7), s(1,3), s(1,6), s(3,7), s(4,6), s(4,7)], [{0,2,4}, {1,5,7}, {2,6,7}, {3,5,6}]),  ([s(1,3), s(1,6), s(2,4), s(2,6), s(3,5), s(4,7), s(5,6)], [{0,2,7}, {0,4,6}, {1,5,7}, {3,6,7}]),  ([s(0,4), s(0,7), s(1,3), s(1,7), s(3,6), s(4,6), s(6,7)], [{0,2,6}, {1,5,6}, {2,4,7}, {3,5,7}]),  ([s(0,2), s(0,6), s(1,6), s(1,7), s(2,7), s(3,6), s(3,7)], [{0,4,7}, {1,3,5}, {2,4,6}, {5,6,7}]),  ([s(0,2), s(0,4), s(1,3), s(1,6), s(2,7), s(3,7), s(4,7)], [{0,6,7}, {1,5,7}, {2,4,6}, {3,5,6}]),  ([s(0,2), s(0,6), s(1,3), s(1,5), s(2,7), s(3,7), s(5,7)], [{0,4,7}, {1,6,7}, {2,4,6}, {3,5,6}]),  ([s(0,4), s(0,6), s(1,3), s(1,6), s(2,4), s(2,6), s(3,7)], [{0,2,7}, {1,5,7}, {3,5,6}, {4,6,7}]),  ([s(0,2), s(0,6), s(1,6), s(1,7), s(2,7), s(5,6), s(5,7)], [{0,4,7}, {1,3,5}, {2,4,6}, {3,6,7}])]theorem W_cover : ∀ e ∈ EL, ∀ f ∈ EL,    ∃ q ∈ W, e ∈ q.1 ∧ f ∈ q.1 := by decide +kerneltheorem W_ok : ∀ q ∈ W, q.2.toFinset.card = 4 ∧    (∀ t ∈ q.2, t ∈ T) ∧    (∀ a ∈ q.2, ∀ b ∈ q.2, a ≠ b → (a ∩ b).card ≤ 1) ∧    (∀ e ∈ q.1, ∀ t ∈ q.2, e ∉ t.sym2) := by decide +kernellemma edge_mem {g : Sym2 (Fin 8)} (h : g ∈ G.edgeSet) : g ∈ EL := by  induction g using Sym2.ind with  | _ a b =>    have h1 := ((SimpleGraph.mem_edgeSet G).mp h).1    exact List.mem_toFinset.mp h1theorem active : ∀ e : Sym2 (Fin 8), e ∈ G.edgeSet →    ∃ t : Finset (Fin 8), G.IsNClique 3 t ∧ e ∈ finite_vertex_set_edge_encoding t := by  intro e he  obtain ⟨t,ht,het⟩ := T_active e (edge_mem he)  exact ⟨t,T_clique t ht,het⟩lemma del_clique {t : Finset (Fin 8)} {e f : Sym2 (Fin 8)}    (h : G.IsNClique 3 t) (he : ¬ ∀ x ∈ e, x ∈ t) (hf : ¬ ∀ x ∈ f, x ∈ t) :    (G.deleteEdges {e,f}).IsNClique 3 t := by  refine ⟨?_, h.card_eq⟩  intro a ha b hb hab  refine (SimpleGraph.deleteEdges_adj).mpr ⟨h.isClique ha hb hab, ?_⟩  intro hmem  simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hmem  rcases hmem with hmem | hmem  · apply he    rw [← hmem]    intro x hx    rcases Sym2.mem_iff.mp hx with rfl | rfl <;> assumption  · apply hf    rw [← hmem]    intro x hx    rcases Sym2.mem_iff.mp hx with rfl | rfl <;> assumptiontheorem stable : ∀ e f : Sym2 (Fin 8), 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 he hf hne  rw [pack_eq]  obtain ⟨q, hq, hqe, hqf⟩ := W_cover e (edge_mem he) f (edge_mem hf)  obtain ⟨hc, ht, hp, hav⟩ := W_ok q hq  unfold simple_graph_triangle_packing_number  refine IsGreatest.csSup_eq ⟨⟨q.2.toFinset, ?_, ?_, hc⟩, ?_⟩  · intro t ht'    have ht'' := List.mem_toFinset.mp ht'    apply del_clique (T_clique t (ht t ht''))    · intro h; exact hav e hqe t ht'' (Finset.mem_sym2_iff.mpr h)    · intro h; exact hav f hqf t ht'' (Finset.mem_sym2_iff.mpr h)  · intro a ha b hb hab    exact hp a (List.mem_toFinset.mp (Finset.mem_coe.mp ha))      b (List.mem_toFinset.mp (Finset.mem_coe.mp hb)) hab  · rintro k ⟨U, hU, hP, rfl⟩    exact nu_le U (fun t ht' => (hU t ht').mono (SimpleGraph.deleteEdges_le _)) hPend In701Freetheorem simple_graph_pair_stable_triangle_active_incidence_two_unpacked_nonbipartite : ∃ (G : SimpleGraph (Fin 8)) (P : Finset (Finset (Fin 8))),    (∀ t ∈ P, G.IsNClique 3 t) ∧    (P : Set (Finset (Fin 8))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧    P.card = simple_graph_triangle_packing_number G ∧ P.biUnion id = Finset.univ ∧    (∀ v : Fin 8, (P.filter (fun t => v ∈ t)).card ≤ 2) ∧    (∀ e f : Sym2 (Fin 8), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f →       simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧    (∀ e : Sym2 (Fin 8), e ∈ G.edgeSet → ∃ t : Finset (Fin 8), G.IsNClique 3 t ∧ e ∈ finite_vertex_set_edge_encoding t) ∧    (∀ f : Fin 8 → Bool, ∃ u v : Fin 8, G.Adj u v ∧      s(u,v) ∉ P.biUnion finite_vertex_set_edge_encoding ∧ f u = f v) := by  refine ⟨In701Free.G,In701Free.P,In701Free.P_clique,In701Free.P_pw,?_,In701Free.P_support,In701Free.P_mult,In701Free.stable,In701Free.active,In701Free.P_nonbip⟩  rw [In701Free.P_card,In701Free.pack_eq]
See it in the graphDiscuss this resultChallenge it