AFTD Auto-Formalizing Theoretical Domains

in701_packing_le_edge_cover

theoremverified

A triangle packing has at most as many triangles as an edge cover.

Statement

theorem in701_packing_le_edge_cover (G : SimpleGraph (Fin 14)) [DecidableRel G.Adj]
    (C : Finset (Sym2 (Fin 14))) (hC : ∀ e ∈ C, e ∈ G.edgeSet)
    (hcover : ∀ t : Finset (Fin 14), G.IsNClique 3 t → ∃ e ∈ C, e ∈ t.sym2)
    (Q : Finset (Finset (Fin 14))) (hQ : ∀ t ∈ Q, G.IsNClique 3 t)
    (hpair : (Q : Set (Finset (Fin 14))).Pairwise (fun s t => (s ∩ t).card ≤ 1)) : Q.card ≤ C.card
Source
Finite graph and certificates from experiments 20940 and 20968; see state/campaigns/triangle_reductions/outside_induced_kernel_in701.md.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

The theorem states that in any graph on 14 vertices, the number of triangles in an edge-disjoint triangle packing $Q$ is at most the number of edges in a triangle edge cover $C$. The proof defines a function $f$ that assigns to each triangle in $Q$ an edge from $C$ contained within it, using classical choice. By `Finset.card_le_card_of_injOn`, it suffices to show that $f$ is injective on $Q$. If two distinct triangles shared the same chosen edge, they would share both of its distinct endpoints, giving an intersection of at least two vertices and contradicting the packing condition.

  1. There is a choice function $f$ that assigns to every triangle $t \in Q$ an edge $f(t) \in C$ such that both endpoints of $f(t)$ lie in $t$.

    Using classical choice on the covering hypothesis `hcover`, define $f(t)$ to select an edge of $C$ contained in $t$ whenever $t$ is a 3-clique in $G$, and a dummy edge otherwise. Since every $t \in Q$ is a 3-clique by `hQ`, `dif_pos` and `Classical.choose_spec` show that $f(t) \in C$ and $f(t) \in t^{\{2\}}$.

    lines 10–15

    uses Classical.choose, dif_pos, Classical.choose_spec

      classical
      let f (t : Finset (Fin 14)) : Sym2 (Fin 14) :=
        if h : G.IsNClique 3 t then Classical.choose (hcover t h) else s(0,0)
      have hchosen : ∀ t ∈ Q, f t ∈ C ∧ f t ∈ t.sym2 := by
        intro t ht
        simpa only [f, dif_pos (hQ t ht)] using Classical.choose_spec (hcover t (hQ t ht))
  2. To show $|Q| \le |C|$, it suffices to show that $f$ maps $Q$ into $C$ and that $f$ is injective on $Q$.

    By `Finset.card_le_card_of_injOn`, the cardinality of a finite set is bounded by that of another if there is an injection from the former into the latter.

    line 16

    uses Finset.card_le_card_of_injOn

      apply Finset.card_le_card_of_injOn f
  3. The function $f$ maps $Q$ into $C$.

    For every triangle $t \in Q$, the property `hchosen` established during the definition of $f$ directly provides $f(t) \in C$.

    lines 17–18

    uses Finset.mem_coe.mp

      · intro t ht
        exact (hchosen t (Finset.mem_coe.mp ht)).1
  4. If two distinct triangles $s, t \in Q$ were to have $f(s) = f(t)$, then both endpoints of the edge $f(s) = s(u, v)$ would belong to both $s$ and $t$.

    Assume for contradiction that $s, t \in Q$ are distinct triangles with $f(s) = f(t)$. By `hchosen`, the edge $f(s)$ is contained in $s$, and $f(t) = f(s)$ is contained in $t$. Writing $f(s)$ as an unordered pair $s(u, v)$ via `Sym2.mk_surjective`, both endpoints $u$ and $v$ belong to both $s$ and $t$ by `Finset.mem_sym2_iff.mp`.

    lines 19–30

    uses Finset.mem_coe.mp, Sym2.mk_surjective, Finset.mem_sym2_iff.mp

      · intro s hs t ht heq
        by_contra hne
        have hsQ := Finset.mem_coe.mp hs
        have htQ := Finset.mem_coe.mp ht
        have hsedge := (hchosen s hsQ).2
        have htedge := (hchosen t htQ).2
        rw [← heq] at htedge
        obtain ⟨⟨u,v⟩,huv⟩ := Sym2.mk_surjective (f s)
        have huv' : s(u,v) = f s := huv
        rw [← huv'] at hsedge htedge
        have huvs : ∀ z ∈ s(u,v), z ∈ s := Finset.mem_sym2_iff.mp hsedge
        have huvt : ∀ z ∈ s(u,v), z ∈ t := Finset.mem_sym2_iff.mp htedge
  5. The vertices $u$ and $v$ are distinct.

    The unordered pair $s(u, v) = f(s)$ belongs to $C$, which is a subset of the edge set of $G$ (by `hC`). Therefore, $u$ and $v$ are adjacent in $G$ (`SimpleGraph.mem_edgeSet`), which implies $u \neq v$ since adjacency is irreflexive.

    lines 31–34

    uses SimpleGraph.mem_edgeSet

        have hadj : G.Adj u v := (SimpleGraph.mem_edgeSet G).mp (by
          rw [huv']
          exact hC _ (hchosen s hsQ).1)
        have huv_ne : u ≠ v := hadj.ne
  6. The function $f$ is injective on $Q$, which implies $|Q| \le |C|$.

    Because $u$ and $v$ are two distinct vertices both belonging to $s \cap t$, the intersection has cardinality strictly greater than 1 (`Finset.one_lt_card.mpr`). But by the packing hypothesis `hpair`, distinct triangles in $Q$ share at most 1 vertex: $|s \cap t| \le 1$. Linear arithmetic (`omega`) derives a contradiction from $|s \cap t| > 1$ and $|s \cap t| \le 1$, proving injectivity and concluding the theorem.

    lines 35–37

    uses Finset.one_lt_card.mpr

        have hi : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,by simp [huvs u (by simp), huvt u (by simp)],v,by simp [huvs v (by simp),huvt v (by simp)],huv_ne⟩
        have hl := hpair hs ht hne
        omega
Classical.choose
Given an existential proof `∃ x, P x`, produces a witness `x`.
Classical.choose_spec
For an existential proof `h : ∃ x, P x`, the chosen witness `Classical.choose h` satisfies `P`.
dif_pos
A dependent if-then-else `if h : c then t else e` simplifies to `t h` when `c` is true.
Finset.card_le_card_of_injOn
If a function `f` maps a finite set `s` into a finite set `t` and is injective on `s`, then `|s| ≤ |t|`.
Finset.mem_coe.mp
Membership of an element in the set coercion of a finset `↑s` implies membership in `s`.
Finset.mem_sym2_iff.mp
If an unordered pair belongs to the 2-element subsets of a finset `s` (`t.sym2`), every vertex in that pair belongs to `s`.
Finset.one_lt_card.mpr
A finset has cardinality strictly greater than 1 if it contains two distinct elements.
SimpleGraph.mem_edgeSet
An unordered pair `s(v, w)` belongs to the edge set of a graph `G` if and only if `v` and `w` are adjacent in `G`.
Sym2.mk_surjective
Every element of `Sym2 α` can be represented as an unordered pair `s(u, v)` of elements `u, v : α`.

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 100000set_option maxHeartbeats 30000000theorem in701_packing_le_edge_cover (G : SimpleGraph (Fin 14)) [DecidableRel G.Adj]    (C : Finset (Sym2 (Fin 14))) (hC : ∀ e ∈ C, e ∈ G.edgeSet)    (hcover : ∀ t : Finset (Fin 14), G.IsNClique 3 t → ∃ e ∈ C, e ∈ t.sym2)    (Q : Finset (Finset (Fin 14))) (hQ : ∀ t ∈ Q, G.IsNClique 3 t)    (hpair : (Q : Set (Finset (Fin 14))).Pairwise (fun s t => (s ∩ t).card ≤ 1)) : Q.card ≤ C.card := by  classical  let f (t : Finset (Fin 14)) : Sym2 (Fin 14) :=    if h : G.IsNClique 3 t then Classical.choose (hcover t h) else s(0,0)  have hchosen : ∀ t ∈ Q, f t ∈ C ∧ f t ∈ t.sym2 := by    intro t ht    simpa only [f, dif_pos (hQ t ht)] using Classical.choose_spec (hcover t (hQ t ht))  apply Finset.card_le_card_of_injOn f  · intro t ht    exact (hchosen t (Finset.mem_coe.mp ht)).1  · intro s hs t ht heq    by_contra hne    have hsQ := Finset.mem_coe.mp hs    have htQ := Finset.mem_coe.mp ht    have hsedge := (hchosen s hsQ).2    have htedge := (hchosen t htQ).2    rw [← heq] at htedge    obtain ⟨⟨u,v⟩,huv⟩ := Sym2.mk_surjective (f s)    have huv' : s(u,v) = f s := huv    rw [← huv'] at hsedge htedge    have huvs : ∀ z ∈ s(u,v), z ∈ s := Finset.mem_sym2_iff.mp hsedge    have huvt : ∀ z ∈ s(u,v), z ∈ t := Finset.mem_sym2_iff.mp htedge    have hadj : G.Adj u v := (SimpleGraph.mem_edgeSet G).mp (by      rw [huv']      exact hC _ (hchosen s hsQ).1)    have huv_ne : u ≠ v := hadj.ne    have hi : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,by simp [huvs u (by simp), huvt u (by simp)],v,by simp [huvs v (by simp),huvt v (by simp)],huv_ne⟩    have hl := hpair hs ht hne    omega
See it in the graphDiscuss this resultChallenge it