simple_graph_triangle_outside_maximum_packing_card_le_one
Every triangle in G shares an edge with any maximum packing, so it has at most one vertex outside the packing support.
Statement
theorem simple_graph_triangle_outside_maximum_packing_card_le_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (T : Finset (Finset V)) (hT : ∀ t ∈ T, G.IsNClique 3 t) (hTp : (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (hTc : T.card = simple_graph_triangle_packing_number G) (t : Finset V) (ht : G.IsNClique 3 t) : (t \ T.biUnion id).card ≤ 1
- Source
- step towards simple_graph_pair_stable_no_good_finite_kernel
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_maximum_triangle_packing_edge_meetsEvery triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
- 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
By the maximality of the packing $T$, every triangle $t$ in $G$ shares an edge (at least two vertices) with some triangle in $T$. Because all vertices of that triangle belong to the packing support $\bigcup T$, the triangle $t$ contains at least two vertices from the support. Since $t$ has only three vertices in total, at most one vertex of $t$ can lie outside the support.
There exists a triangle $q$ in the packing $T$ sharing at least two vertices with $t$.
By the lemma `simple_graph_maximum_triangle_packing_edge_meets`, any triangle in $G$ must share an edge (at least two vertices) with some triangle in a maximum triangle packing $T$. We obtain such a triangle $q \in T$ with $|q \cap t| \ge 2$.
uses
simple_graph_maximum_triangle_packing_edge_meetsclassical obtain ⟨q,hq,hqmeet⟩ := simple_graph_maximum_triangle_packing_edge_meets G T hT hTp hTc t htThe shared vertices $q \cap t$ lie in the packing support, so $|q \cap t| \le |t \cap \bigcup T|$.
Any vertex $x \in q \cap t$ belongs to $t$ and to $q$. Since $q \in T$, $x$ belongs to the packing support $\bigcup T$ (written `T.biUnion id`). Thus $q \cap t \subseteq t \cap \bigcup T$, which implies $|q \cap t| \le |t \cap \bigcup T|$ by subset inclusion.
uses
Finset.mem_inter.mp,Finset.mem_inter.mpr,Finset.mem_biUnion.mpr,Finset.card_le_cardhave hsub : q ∩ t ⊆ t ∩ T.biUnion id := by intro x hx obtain ⟨hxq,hxt⟩ := Finset.mem_inter.mp hx exact Finset.mem_inter.mpr ⟨hxt, Finset.mem_biUnion.mpr ⟨q,hq,hxq⟩⟩ have hcard := Finset.card_le_card hsub
The number of vertices of $t$ outside the packing support plus the number inside equals 3.
Partitioning the vertices of $t$ according to whether they lie in the packing support gives $|t \setminus \bigcup T| + |t \cap \bigcup T| = |t|$. Because $t$ is a 3-clique, its cardinality is 3, yielding the identity with 3 on the right-hand side.
uses
Finset.card_sdiff_add_card_interhave hsum := Finset.card_sdiff_add_card_inter t (T.biUnion id) rw [ht.card_eq] at hsum
At most one vertex of $t$ lies outside the packing support. automation
Linear arithmetic (`omega`) closes the goal from the partition equation $|t \setminus \bigcup T| + |t \cap \bigcup T| = 3$ and the lower bound $|t \cap \bigcup T| \ge |q \cap t| \ge 2$.
omega
simple_graph_maximum_triangle_packing_edge_meets- In a graph $G$, every triangle shares at least two vertices with some triangle in any maximum triangle packing.
Finset.mem_inter.mp- If an element belongs to the intersection of two finite sets, it belongs to both sets.
Finset.mem_inter.mpr- If an element belongs to both finite sets, it belongs to their intersection.
Finset.mem_biUnion.mpr- If an element belongs to a member set of a indexed family, it belongs to the union of that family.
Finset.card_le_card- If a finite set is a subset of another, its cardinality is less than or equal to that of the superset.
Finset.card_sdiff_add_card_inter- For any finite sets $s$ and $t$, the size of their difference plus the size of their intersection equals the size of $s$.
- The packing support is represented formally as `T.biUnion id`, which is the union $\bigcup T$ of all vertex sets in the packing $T$.
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.
/-- Every triangle in G shares an edge with any maximum packing, so it has at most one vertex outside the packing support. -/theorem simple_graph_triangle_outside_maximum_packing_card_le_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (T : Finset (Finset V)) (hT : ∀ t ∈ T, G.IsNClique 3 t) (hTp : (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (hTc : T.card = simple_graph_triangle_packing_number G) (t : Finset V) (ht : G.IsNClique 3 t) : (t \ T.biUnion id).card ≤ 1 := by classical obtain ⟨q,hq,hqmeet⟩ := simple_graph_maximum_triangle_packing_edge_meets G T hT hTp hTc t ht have hsub : q ∩ t ⊆ t ∩ T.biUnion id := by intro x hx obtain ⟨hxq,hxt⟩ := Finset.mem_inter.mp hx exact Finset.mem_inter.mpr ⟨hxt, Finset.mem_biUnion.mpr ⟨q,hq,hxq⟩⟩ have hcard := Finset.card_le_card hsub have hsum := Finset.card_sdiff_add_card_inter t (T.biUnion id) rw [ht.card_eq] at hsum omega