AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_packing_decreases_of_high_codegree

theoremverified

Deleting an edge with more than twice the maximum triangle packing number common neighbors strictly decreases the packing number.

Statement

theorem simple_graph_triangle_packing_decreases_of_high_codegree
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (u v : V) (huv : G.Adj u v)
    (hlarge : 2 * simple_graph_triangle_packing_number G <
      ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card) :
    simple_graph_triangle_packing_number (G.deleteEdges {s(u,v)}) < simple_graph_triangle_packing_number G
Source
Structural helper for the triangle packing-cover campaign; related matching-cover reductions are in https://arxiv.org/abs/2610.15269, Lemma 2.3. Finite checks and limitations are recorded in state/campaigns/triangle_reductions/high_codegree_route_in512.md.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof proceeds by contradiction. If deleting the edge {u, v} does not strictly decrease the triangle packing number, then the remaining graph H = G \ {{u, v}} has a maximum triangle packing P of size equal to ν(G), making P a maximum triangle packing of G as well. Since the edge {u, v} was deleted, no triangle in P can contain both u and v. However, any maximal triangle packing avoiding {u, v} forces the codegree of u and v to be at most 2|P| = 2ν(G), contradicting the hypothesis that u and v have strictly more than 2ν(G) common neighbors.

  1. The graph H obtained by deleting the edge {u, v} is a subgraph of G, so its triangle packing number satisfies ν(H) ≤ ν(G).

    Let H = G \ {{u, v}}. Since deleting edges produces a subgraph (H ≤ G by SimpleGraph.deleteEdges_le), monotonicity of the triangle packing number (simple_graph_triangle_packing_number_mono) implies that ν(H) ≤ ν(G).

    lines 11–15

    uses SimpleGraph.deleteEdges_le, simple_graph_triangle_packing_number_mono

      classical
      let H := G.deleteEdges {s(u,v)}
      have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(u,v)}
      have hle : simple_graph_triangle_packing_number H ≤ simple_graph_triangle_packing_number G :=
        simple_graph_triangle_packing_number_mono G H hHG
  2. Assuming the packing number does not strictly decrease implies ν(H) = ν(G).

    Assume for contradiction that ν(H) < ν(G) does not hold. Because ν(H) ≤ ν(G), linear integer arithmetic implies that ν(H) = ν(G).

    lines 16–18

      by_contra hn
      change ¬ simple_graph_triangle_packing_number H < simple_graph_triangle_packing_number G at hn
      have heq : simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G := by omega
  3. There exists an edge-disjoint triangle packing P in H achieving the maximum size |P| = ν(H).

    Let A be the set of sizes of edge-disjoint triangle packings in H. The empty packing shows that 0 ∈ A, so A is nonempty. Moreover, every packing is a family of subsets of V, so its size is bounded by the total number of subsets |Finset V| via Finset.card_le_univ. By Nat.sSup_mem, the supremum ν(H) = sSup A is attained by some packing P in H with |P| = ν(H).

    lines 19–26

    uses Finset.card_le_univ, Nat.sSup_mem

      let A : Set ℕ := {n | ∃ P : Finset (Finset V), (∀ t ∈ P, H.IsNClique 3 t) ∧
        (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = n}
      have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩
      have hbdd : BddAbove A := by
        refine ⟨Fintype.card (Finset V), ?_⟩
        rintro n ⟨P, _, _, rfl⟩
        exact Finset.card_le_univ P
      obtain ⟨P, hPH, hpair, hcard⟩ := Nat.sSup_mem hne hbdd
  4. P is a maximum triangle packing of G, so every triangle in G shares an edge with some triangle in P.

    Since |P| = ν(H) and ν(H) = ν(G), we have |P| = ν(G). Furthermore, because H ≤ G, every triangle in H is also a triangle in G. Thus P is a triangle packing in G of maximum possible size ν(G). By simple_graph_maximum_triangle_packing_edge_meets, every triangle in G must share at least two vertices with some triangle in P.

    lines 27–33

    uses simple_graph_maximum_triangle_packing_edge_meets

      have hcard' : P.card = simple_graph_triangle_packing_number G := by
        change P.card = simple_graph_triangle_packing_number H at hcard
        omega
      have hPG : ∀ t ∈ P, G.IsNClique 3 t := by
        intro t ht
        exact (hPH t ht).mono hHG
      have hmax := simple_graph_maximum_triangle_packing_edge_meets G P hPG hpair hcard'
  5. No triangle in P contains both u and v.

    Suppose some triangle s ∈ P contains both u and v. Since s is a clique in H, u and v would be adjacent in H. However, the edge {u, v} was deleted to form H, so SimpleGraph.deleteEdges_adj.mp implies that {u, v} cannot be an edge of H, giving a contradiction.

    lines 34–38

    uses SimpleGraph.deleteEdges_adj.mp

      have havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s) := by
        intro s hs hmem
        have hadj : H.Adj u v := (hPH s hs).isClique hmem.1 hmem.2 (G.ne_of_adj huv)
        have := (SimpleGraph.deleteEdges_adj.mp hadj).2
        exact this (by simp)
  6. The number of common neighbors of u and v is at most 2ν(G), contradicting the hypothesis.

    Because P is a maximal triangle packing in G that avoids the edge {u, v}, simple_graph_maximal_packing_common_neighbors_le implies that the number of common neighbors of u and v in G is at most 2|P| = 2ν(G). But the hypothesis hlarge asserts that the common neighbor count is strictly greater than 2ν(G). Linear arithmetic closes the goal with a contradiction.

    lines 39–41

    uses simple_graph_maximal_packing_common_neighbors_le

      have hsmall := simple_graph_maximal_packing_common_neighbors_le G u v P huv hPG hmax havoid
      rw [hcard'] at hsmall
      omega
SimpleGraph.deleteEdges_le
Deleting a set of edges from a graph results in a subgraph of the original graph.
simple_graph_triangle_packing_number_mono
If H is a subgraph of G, the triangle packing number of H is at most that of G.
Finset.card_le_univ
The cardinality of any finite subset of α is at most the total cardinality of α.
Nat.sSup_mem
Any nonempty, bounded-above set of natural numbers contains its supremum (maximum).
simple_graph_maximum_triangle_packing_edge_meets
In any maximum triangle packing, every triangle in the graph shares at least an edge (two vertices) with some triangle in the packing.
SimpleGraph.deleteEdges_adj.mp
If an edge belongs to a graph obtained by deleting a set of edges, then it belonged to the original graph and was not in the deleted set.
simple_graph_maximal_packing_common_neighbors_le
If a maximal triangle packing avoids an edge {u, v}, then the number of common neighbors of u and v is at most twice the size of the packing.

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_triangle_packing_decreases_of_high_codegree    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (u v : V) (huv : G.Adj u v)    (hlarge : 2 * simple_graph_triangle_packing_number G <      ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card) :    simple_graph_triangle_packing_number (G.deleteEdges {s(u,v)}) < simple_graph_triangle_packing_number G := by  classical  let H := G.deleteEdges {s(u,v)}  have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(u,v)}  have hle : simple_graph_triangle_packing_number H ≤ simple_graph_triangle_packing_number G :=    simple_graph_triangle_packing_number_mono G H hHG  by_contra hn  change ¬ simple_graph_triangle_packing_number H < simple_graph_triangle_packing_number G at hn  have heq : simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G := by omega  let A : Set ℕ := {n | ∃ P : Finset (Finset V), (∀ t ∈ P, H.IsNClique 3 t) ∧    (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = n}  have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩  have hbdd : BddAbove A := by    refine ⟨Fintype.card (Finset V), ?_⟩    rintro n ⟨P, _, _, rfl⟩    exact Finset.card_le_univ P  obtain ⟨P, hPH, hpair, hcard⟩ := Nat.sSup_mem hne hbdd  have hcard' : P.card = simple_graph_triangle_packing_number G := by    change P.card = simple_graph_triangle_packing_number H at hcard    omega  have hPG : ∀ t ∈ P, G.IsNClique 3 t := by    intro t ht    exact (hPH t ht).mono hHG  have hmax := simple_graph_maximum_triangle_packing_edge_meets G P hPG hpair hcard'  have havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s) := by    intro s hs hmem    have hadj : H.Adj u v := (hPH s hs).isClique hmem.1 hmem.2 (G.ne_of_adj huv)    have := (SimpleGraph.deleteEdges_adj.mp hadj).2    exact this (by simp)  have hsmall := simple_graph_maximal_packing_common_neighbors_le G u v P huv hPG hmax havoid  rw [hcard'] at hsmall  omega
See it in the graphDiscuss this resultChallenge it