AFTD Auto-Formalizing Theoretical Domains

finite_five_vertex_triangle_packing_card_le_two

theoremverified

Any family of three-element subsets of a five-element set with pairwise intersections of at most one has at most two members.

Statement

theorem finite_five_vertex_triangle_packing_card_le_two (P : Finset (Finset (Fin 5))) (htri : ∀ t ∈ P, t.card = 3) (hpack : (P : Set (Finset (Fin 5))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : P.card ≤ 2
Source
Five-vertex block bound for simple_graph_dense_high_degree_unforced_internal_k4_anchor_counterexample.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by contradiction using finite exhaustive verification. All $\binom{5}{3} = 10$ potential triangles on five vertices are explicitly enumerated, and an exhaustive check confirms that every 3-element subset appears in this list. A second exhaustive computation verifies that no three distinct triangles from this list can have pairwise intersections of size at most one. Assuming for contradiction that a packing contains at least three distinct triangles, their pairwise intersections must all have size at most one, which contradicts the exhaustive check.

  1. Every 3-element subset of a 5-element set belongs to the explicit list `in704_triangles5`.

    The lemma `in704_triangles5_complete` asserts that any subset of $\{0,1,2,3,4\}$ with cardinality 3 is one of the ten triangles enumerated in `in704_triangles5`. This universal statement over all subsets is verified by exhaustive computation via `decide`, and then specialized to the given subset $t$ with hypothesis $|t| = 3$.

    lines 7–9

    lemma in704_triangles5_complete (t : Finset (Fin 5)) (ht : t.card = 3) : t ∈ in704_triangles5 := by
      have h : ∀ t : Finset (Fin 5), t.card = 3 → t ∈ in704_triangles5 := by decide
      exact h t ht
  2. No three distinct triangles from `in704_triangles5` can have all pairwise intersections of size at most 1. automation

    The lemma `in704_three_impossible` checks that for any triple of triangles $a, b, c \in \text{in704\_triangles5}$ whose pairwise intersections each have at most one element, at least two of the triangles must be identical. Since there are only $10^3 = 1000$ triples to test, this exhaustive property is proved directly by Lean's computational decision procedure `decide`.

    lines 11–15

    lemma in704_three_impossible :
        ∀ a ∈ in704_triangles5, ∀ b ∈ in704_triangles5, ∀ c ∈ in704_triangles5,
          (a ∩ b).card ≤ 1 → (a ∩ c).card ≤ 1 → (b ∩ c).card ≤ 1 →
          a = b ∨ a = c ∨ b = c := by
      decide
  3. Assuming for contradiction that $|P| > 2$, the family $P$ contains three pairwise distinct triangles $a, b, c$.

    We proceed by contradiction (`by_contra`) by assuming $\neg(|P| \le 2)$. The linear arithmetic tactic `omega` deduces that $|P| > 2$. Applying `Finset.two_lt_card.mp` then extracts three distinct elements $a, b, c \in P$ with $a \ne b$, $a \ne c$, and $b \ne c$.

    lines 21–23

    uses Finset.two_lt_card.mp

      by_contra h
      have hcard : 2 < P.card := by omega
      obtain ⟨a,ha,b,hb,c,hc,hab,hac,hbc⟩ := Finset.two_lt_card.mp hcard
  4. The pairwise intersections $|a \cap b|$, $|a \cap c|$, and $|b \cap c|$ each have cardinality at most 1.

    Since $P$ is a packing family (`hpack`), any two distinct members have an intersection of size at most 1. Applying this hypothesis to the distinct pairs $(a, b)$, $(a, c)$, and $(b, c)$ yields $|a \cap b| \le 1$, $|a \cap c| \le 1$, and $|b \cap c| \le 1$.

    lines 24–26

      have hab' := hpack ha hb hab
      have hac' := hpack ha hc hac
      have hbc' := hpack hb hc hbc
  5. The triangles $a, b, c$ cannot be pairwise distinct, completing the contradiction.

    Each member of $P$ has cardinality 3 (`htri`), so by `in704_triangles5_complete` each of $a, b, c$ belongs to `in704_triangles5`. Applying `in704_three_impossible` to $a, b, c$ and their intersection bounds produces the disjunction $a = b \lor a = c \lor b = c$. In each of the three cases, this directly contradicts one of the distinctness hypotheses $a \ne b$, $a \ne c$, or $b \ne c$.

    lines 27–32

    uses in704_three_impossible, in704_triangles5_complete

      rcases in704_three_impossible a (in704_triangles5_complete a (htri a ha))
          b (in704_triangles5_complete b (htri b hb))
          c (in704_triangles5_complete c (htri c hc)) hab' hac' hbc' with h | h | h
      · exact hab h
      · exact hac h
      · exact hbc h
  6. Any packing of triangles on a 5-element set has cardinality at most 2.

    The top-level theorem `finite_five_vertex_triangle_packing_card_le_two` directly delegates to the proven namespace result `In704Five.in704_five_triangle_packing_card_le_two` with the family $P$ and hypotheses.

    lines 36–37

    uses In704Five.in704_five_triangle_packing_card_le_two

    theorem finite_five_vertex_triangle_packing_card_le_two (P : Finset (Finset (Fin 5))) (htri : ∀ t ∈ P, t.card = 3) (hpack : (P : Set (Finset (Fin 5))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : P.card ≤ 2 := by
      exact In704Five.in704_five_triangle_packing_card_le_two P htri hpack
Finset.two_lt_card.mp
If a finite set has cardinality strictly greater than 2, it contains at least three pairwise distinct elements.
in704_triangles5_complete
Every 3-element subset of a 5-element set belongs to the explicit list `in704_triangles5` of 10 triangles.
in704_three_impossible
If three triangles from `in704_triangles5` have pairwise intersections of cardinality at most 1, then at least two of them must be equal.
In704Five.in704_five_triangle_packing_card_le_two
Any family of 3-element subsets of a 5-element set with pairwise intersections of cardinality at most 1 has cardinality at most 2.

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

set_option maxRecDepth 10000set_option maxHeartbeats 4000000namespace In704Fivedef in704_triangles5 : Finset (Finset (Fin 5)) :=  {{0,1,2},{0,1,3},{0,1,4},{0,2,3},{0,2,4},{0,3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}}lemma in704_triangles5_complete (t : Finset (Fin 5)) (ht : t.card = 3) : t ∈ in704_triangles5 := by  have h : ∀ t : Finset (Fin 5), t.card = 3 → t ∈ in704_triangles5 := by decide  exact h t htlemma in704_three_impossible :    ∀ a ∈ in704_triangles5, ∀ b ∈ in704_triangles5, ∀ c ∈ in704_triangles5,      (a ∩ b).card ≤ 1 → (a ∩ c).card ≤ 1 → (b ∩ c).card ≤ 1 →      a = b ∨ a = c ∨ b = c := by  decidetheorem in704_five_triangle_packing_card_le_two (P : Finset (Finset (Fin 5)))    (htri : ∀ t ∈ P, t.card = 3)    (hpack : (P : Set (Finset (Fin 5))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) :    P.card ≤ 2 := by  by_contra h  have hcard : 2 < P.card := by omega  obtain ⟨a,ha,b,hb,c,hc,hab,hac,hbc⟩ := Finset.two_lt_card.mp hcard  have hab' := hpack ha hb hab  have hac' := hpack ha hc hac  have hbc' := hpack hb hc hbc  rcases in704_three_impossible a (in704_triangles5_complete a (htri a ha))      b (in704_triangles5_complete b (htri b hb))      c (in704_triangles5_complete c (htri c hc)) hab' hac' hbc' with h | h | h  · exact hab h  · exact hac h  · exact hbc hend In704Fivetheorem finite_five_vertex_triangle_packing_card_le_two (P : Finset (Finset (Fin 5))) (htri : ∀ t ∈ P, t.card = 3) (hpack : (P : Set (Finset (Fin 5))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : P.card ≤ 2 := by  exact In704Five.in704_five_triangle_packing_card_le_two P htri hpack
See it in the graphDiscuss this resultChallenge it