AFTD Auto-Formalizing Theoretical Domains

simple_graph_exists_support_maximum_triangle_packing

theoremverified

Every finite graph has a maximum triangle packing whose vertex support has maximum cardinality among all maximum triangle packings.

Statement

theorem simple_graph_exists_support_maximum_triangle_packing (n : ℕ) (G : SimpleGraph (Fin n)) : ∃ P : Finset (Finset (Fin n)), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G ∧ ∀ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, G.IsNClique 3 t) → (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) → Q.card = P.card → (Q.biUnion id).card ≤ (P.biUnion id).card
Source
Finite support-maximal selection used in the general pair-stable forced-K4 reduction; no novelty claim.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The triangle packing number of a finite graph is the maximum cardinality of an edge-disjoint collection of triangles. Because the graph is finite, the set of sizes of all triangle packings is non-empty and bounded above, guaranteeing the existence of a maximum packing. The collection of all maximum triangle packings is therefore a non-empty finite set, so we can select one that maximizes the cardinality of its vertex support.

  1. The set A of sizes of all triangle packings of G is non-empty and bounded above.

    We enable classical logic and define A ⊆ ℕ as the set of cardinalities of all triangle packings (families of 3-cliques pairwise intersecting in at most one vertex). The empty set is vacuously a triangle packing of size 0, so 0 ∈ A and A is non-empty. Since every packing is a family of vertex subsets of G, its cardinality is bounded by the total number of subsets of the vertex set, so A is bounded above.

    lines 6–14

    uses Finset.card_le_univ

      classical
      let A : Set ℕ := {k | ∃ P : Finset (Finset (Fin n)),
        (∀ t ∈ P, G.IsNClique 3 t) ∧
        (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = k}
      have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩
      have hbdd : BddAbove A := by
        refine ⟨Fintype.card (Finset (Fin n)), ?_⟩
        rintro k ⟨P, _, _, rfl⟩
        exact Finset.card_le_univ P
  2. There exists a triangle packing P₀ achieving the graph's triangle packing number.

    Since A is a non-empty, bounded-above set of natural numbers, its supremum belongs to A by Nat.sSup_mem. By definition, the triangle packing number of G is precisely sSup A, so there exists a packing P₀ whose cardinality equals this maximum packing number.

    lines 15–18

    uses Nat.sSup_mem

      obtain ⟨P₀,h₀tri,h₀pair,h₀card⟩ := Nat.sSup_mem hne hbdd
      have h₀max : P₀.card = simple_graph_triangle_packing_number G := by
        change P₀.card = simple_graph_triangle_packing_number G at h₀card
        exact h₀card
  3. The collection F of all maximum triangle packings is a non-empty finite set.

    We define F as the subcollection of the finite universe of families of vertex subsets consisting of all triangle packings of size equal to the triangle packing number. Because P₀ satisfies all these conditions, P₀ ∈ F, which proves F is non-empty.

    lines 19–26

    uses Finset.mem_filter, Finset.mem_univ, true_and

      let F : Finset (Finset (Finset (Fin n))) := Finset.univ.filter (fun P =>
        (∀ t ∈ P, G.IsNClique 3 t) ∧
        (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧
        P.card = simple_graph_triangle_packing_number G)
      have hF : F.Nonempty := by
        refine ⟨P₀, ?_⟩
        simp only [F, Finset.mem_filter, Finset.mem_univ, true_and]
        exact ⟨h₀tri,h₀pair,h₀max⟩
  4. There exists a maximum triangle packing P whose vertex support has maximum cardinality among all maximum triangle packings.

    Because F is a non-empty finite set, Finset.exists_max_image implies that the function measuring the size of the vertex support, |⋃ P| = (P.biUnion id).card, achieves its maximum on F at some packing P. Expanding the definition of membership in F shows that P is an edge-disjoint collection of triangles of maximum cardinality.

    lines 27–31

    uses Finset.exists_max_image, Finset.mem_filter, Finset.mem_univ, true_and

      obtain ⟨P,hP,hmax⟩ := Finset.exists_max_image F (fun P => (P.biUnion id).card) hF
      have hP' : (∀ t ∈ P, G.IsNClique 3 t) ∧
          (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧
          P.card = simple_graph_triangle_packing_number G := by
        simpa only [F, Finset.mem_filter, Finset.mem_univ, true_and] using hP
  5. P is a maximum triangle packing whose vertex support has cardinality at least that of any other maximum packing.

    We provide P as the witness. Its packing and maximality properties were established in the previous step. For any other triangle packing Q with |Q| = |P|, Q also achieves the maximum packing number and therefore belongs to F. By the maximality of P on F, the vertex support of Q has cardinality at most that of P.

    lines 32–36

    uses Finset.mem_filter, Finset.mem_univ, true_and

      refine ⟨P,hP'.1,hP'.2.1,hP'.2.2, ?_⟩
      intro Q hQtri hQpair hQcard
      apply hmax Q
      simp only [F, Finset.mem_filter, Finset.mem_univ, true_and]
      exact ⟨hQtri,hQpair,hQcard.trans hP'.2.2⟩
Finset.card_le_univ
the cardinality of any finite subset of a finite type is at most the cardinality of the ambient type
Finset.exists_max_image
any function from a non-empty finite set into a linearly ordered type attains its maximum
Finset.mem_filter
an element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate
Finset.mem_univ
every element of a finite type belongs to the universal finset univ
Nat.sSup_mem
if a set of natural numbers is non-empty and bounded above, its supremum belongs to the set
true_and
conjunction with True simplifies to the proposition itself

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 10000set_option maxHeartbeats 3000000theorem simple_graph_exists_support_maximum_triangle_packing (n : ℕ) (G : SimpleGraph (Fin n)) : ∃ P : Finset (Finset (Fin n)), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G ∧ ∀ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, G.IsNClique 3 t) → (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) → Q.card = P.card → (Q.biUnion id).card ≤ (P.biUnion id).card := by  classical  let A : Set ℕ := {k | ∃ P : Finset (Finset (Fin n)),    (∀ t ∈ P, G.IsNClique 3 t) ∧    (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = k}  have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩  have hbdd : BddAbove A := by    refine ⟨Fintype.card (Finset (Fin n)), ?_⟩    rintro k ⟨P, _, _, rfl⟩    exact Finset.card_le_univ P  obtain ⟨P₀,h₀tri,h₀pair,h₀card⟩ := Nat.sSup_mem hne hbdd  have h₀max : P₀.card = simple_graph_triangle_packing_number G := by    change P₀.card = simple_graph_triangle_packing_number G at h₀card    exact h₀card  let F : Finset (Finset (Finset (Fin n))) := Finset.univ.filter (fun P =>    (∀ t ∈ P, G.IsNClique 3 t) ∧    (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧    P.card = simple_graph_triangle_packing_number G)  have hF : F.Nonempty := by    refine ⟨P₀, ?_⟩    simp only [F, Finset.mem_filter, Finset.mem_univ, true_and]    exact ⟨h₀tri,h₀pair,h₀max⟩  obtain ⟨P,hP,hmax⟩ := Finset.exists_max_image F (fun P => (P.biUnion id).card) hF  have hP' : (∀ t ∈ P, G.IsNClique 3 t) ∧      (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧      P.card = simple_graph_triangle_packing_number G := by    simpa only [F, Finset.mem_filter, Finset.mem_univ, true_and] using hP  refine ⟨P,hP'.1,hP'.2.1,hP'.2.2, ?_⟩  intro Q hQtri hQpair hQcard  apply hmax Q  simp only [F, Finset.mem_filter, Finset.mem_univ, true_and]  exact ⟨hQtri,hQpair,hQcard.trans hP'.2.2⟩
See it in the graphDiscuss this resultChallenge it