simple_graph_pair_stable_triangle_active_incidence_two_unpacked_nonbipartite
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
- simple_graph_in693_ten_seed_packing_numberThe concrete ten-vertex five-link seed has triangle packing number eight.
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- 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 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.
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.
uses
Sym2.eq_swapdef 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 ∧ _ ≠ _))
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).
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
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).
uses
in693_maxC_bound,maxC_eqdef 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
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).
uses
IsGreatest.csSup_eq,nu_le,P_clique,P_pw,P_cardtheorem 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
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.
uses
clique_mem,T_cliquetheorem 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⟩
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).
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
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).
theorem T_active : ∀ e ∈ EL, ∃ t ∈ T, e ∈ finite_vertex_set_edge_encoding t := by decide +kernel
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).
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
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.
uses
Sym2.ind,SimpleGraph.mem_edgeSet,T_active,edge_mem,T_cliquelemma 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⟩
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).
uses
SimpleGraph.deleteEdges_adjlemma 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
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).
uses
pack_eq,W_cover,edge_mem,W_ok,IsGreatest.csSup_eq,del_clique,T_clique,nu_le,SimpleGraph.deleteEdges_letheorem 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
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.
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_eqtheorem 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.
- Exhaustive finite checks (characterizing the 20 triangles, the maximum packing size bound, support-maximality, vertex multiplicity, non-bipartiteness of unpacked edges, and covering of edge pairs by witness packings) are verified by the Lean kernel via `decide +kernel`.
- Two-edge stability of the packing number is established by exhibiting a precomputed family of 17 witness packings $W$, each avoiding a specified subset of edges, such that every pair of graph edges is covered by at least one witness.
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 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]