finite_five_vertex_triangle_packing_card_le_two
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.
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$.
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
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`.
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
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$.
uses
Finset.two_lt_card.mpby_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
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$.
have hab' := hpack ha hb hab have hac' := hpack ha hc hac have hbc' := hpack hb hc hbc
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$.
uses
in704_three_impossible,in704_triangles5_completercases 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
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.
uses
In704Five.in704_five_triangle_packing_card_le_twotheorem 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.
- The classification in `in704_three_impossible` (line 15) and the completeness of the candidate triangle list in `in704_triangles5_complete` (line 8) are verified mechanically by Lean's `decide` tactic, which evaluates all combinations by finite computation.
- The deduction that $2 < |P|$ from $\neg(|P| \le 2)$ (line 22) is discharged automatically by the linear integer arithmetic tactic `omega`.
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.
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