AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_outside_maximum_packing_card_le_one

theoremverified

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

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.

  1. 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$.

    lines 9–10

    uses simple_graph_maximum_triangle_packing_edge_meets

      classical
      obtain ⟨q,hq,hqmeet⟩ := simple_graph_maximum_triangle_packing_edge_meets G T hT hTp hTc t ht
  2. The 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.

    lines 11–15

    uses Finset.mem_inter.mp, Finset.mem_inter.mpr, Finset.mem_biUnion.mpr, Finset.card_le_card

      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
  3. 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.

    lines 16–17

    uses Finset.card_sdiff_add_card_inter

      have hsum := Finset.card_sdiff_add_card_inter t (T.biUnion id)
      rw [ht.card_eq] at hsum
  4. 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$.

    line 18

      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$.

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

/-- 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
See it in the graphDiscuss this resultChallenge it