AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_number_mono

theoremverified

Triangle cover number is monotone under subgraph inclusion: if H ≤ G, then τ(H) ≤ τ(G).

Statement

theorem simple_graph_triangle_cover_number_mono {V : Type*} [Fintype V]
    (G H : SimpleGraph V) (hle : H ≤ G) :
    simple_graph_triangle_cover_number H ≤ simple_graph_triangle_cover_number G
Source
step towards simple_graph_triangle_cover_number_le_two_mul_packing_number
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The triangle cover number τ(G) is the minimum size of an edge set that intersects every triangle (3-clique) in G. To prove that τ(H) ≤ τ(G) whenever H ≤ G, the argument selects a minimum triangle cover F of G and restricts it to H by setting F' = F ∩ E(H). Because every triangle in H is also a triangle in G, its covering edge in F has both endpoints in H, forcing that edge to belong to H; hence F' covers all triangles in H, giving τ(H) ≤ |F'| ≤ |F| = τ(G).

  1. The set of sizes of triangle covers of G is nonempty.

    Working classically, the proof shows that the set of triangle cover sizes is nonempty by demonstrating that the full edge set of G (filtered from the set of all pairs) is a triangle cover. Every edge in this set is an edge of G by definition. Furthermore, any 3-clique t in G contains three distinct vertices x, y, z; since they form a clique, x and y are adjacent in G, so the edge s(x, y) is an edge of G with both endpoints in t.

    lines 5–20

    uses Finset.card_eq_three.1, Finset.mem_filter, Finset.mem_univ, Sym2.mem_iff

      classical
      have hne : {n | ∃ F : Finset (Sym2 V), (∀ e ∈ F, e ∈ G.edgeSet) ∧
          (∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t) ∧ F.card = n}.Nonempty := by
        refine ⟨_, Finset.univ.filter (· ∈ G.edgeSet), ?_, ?_, rfl⟩
        · intro e he
          rw [Finset.mem_filter] at he
          exact he.2
        · intro t ht
          obtain ⟨x, y, z, hxy, -, -, rfl⟩ := Finset.card_eq_three.1 ht.card_eq
          have hadj : G.Adj x y := ht.isClique (by simp) (by simp) hxy
          refine ⟨s(x, y), ?_, ?_⟩
          · rw [Finset.mem_filter]
            exact ⟨Finset.mem_univ _, hadj⟩
          · intro v hv
            simp only [Sym2.mem_iff] at hv
            rcases hv with rfl | rfl <;> simp
  2. There exists a minimum triangle cover F of G, and its restriction F' to edges of H consists entirely of edges of H.

    Since the set of triangle cover sizes of G is nonempty, its infimum is attained by some finset F, meaning |F| = τ(G) and F covers all triangles of G. We define F' by restricting F to the edges of H (filtering by `· ∈ H.edgeSet`). By definition of the filter, every edge in F' is an edge of H.

    lines 21–27

    uses Nat.sInf_mem, Finset.mem_filter

      obtain ⟨F, hFedge, hFcover, hFcard⟩ := Nat.sInf_mem hne
      change F.card = simple_graph_triangle_cover_number G at hFcard
      set F' : Finset (Sym2 V) := F.filter (· ∈ H.edgeSet)
      have hF'edge : ∀ e ∈ F', e ∈ H.edgeSet := by
        intro e he
        rw [Finset.mem_filter] at he
        exact he.2
  3. F' covers every triangle in H.

    Given any triangle t in H, since H ≤ G, t is also a triangle in G. Thus F contains an edge e with both endpoints in t. Decomposing e into an unordered pair s(u, v), the fact that e is an edge of G implies u ≠ v. Since both u and v belong to the clique t in H, they are adjacent in H. Therefore, e is an edge of H and belongs to F', showing that F' covers t.

    lines 28–39

    uses Sym2.ind, Finset.mem_filter

      have hF'cover : ∀ t : Finset V, H.IsNClique 3 t → ∃ e ∈ F', ∀ x ∈ e, x ∈ t := by
        intro t ht
        obtain ⟨e, heF, het⟩ := hFcover t (ht.mono hle)
        induction' e using Sym2.ind with u v
        have heG : G.Adj u v := hFedge s(u, v) heF
        have hne : u ≠ v := G.ne_of_adj heG
        have hu : u ∈ t := het u (by simp)
        have hv : v ∈ t := het v (by simp)
        have hadj : H.Adj u v := ht.isClique hu hv hne
        refine ⟨s(u, v), ?_, het⟩
        rw [Finset.mem_filter]
        exact ⟨heF, hadj⟩
  4. The triangle cover number of H is at most that of G: τ(H) ≤ τ(G).

    Because F' is a valid triangle cover of H, its size |F'| belongs to the set of cover sizes of H, which implies τ(H) ≤ |F'| by definition of the infimum. Moreover, as F' was obtained by filtering F, we have |F'| ≤ |F|. Since |F| = τ(G), transitivity yields τ(H) ≤ τ(G).

    lines 40–44

    uses Nat.sInf_le, Finset.card_filter_le

      have hHle : simple_graph_triangle_cover_number H ≤ F'.card := by
        apply Nat.sInf_le
        exact ⟨F', hF'edge, hF'cover, rfl⟩
      rw [← hFcard]
      exact hHle.trans (Finset.card_filter_le _ _)
Finset.card_eq_three.1
A finite set has cardinality 3 if and only if (in the forward direction) it consists of three distinct elements.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set `Finset.univ`.
Sym2.mem_iff
An element belongs to the unordered pair s(a, b) if and only if it is equal to a or equal to b.
Nat.sInf_mem
The infimum of a nonempty set of natural numbers is an element of that set.
Sym2.ind
Every unordered pair in Sym2 α is of the form s(x, y) for some x, y in α.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in the set.
Finset.card_filter_le
Filtering a finite set yields a subset whose cardinality is at most the original cardinality.

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

/-- Triangle cover number is monotone under subgraph inclusion: if H ≤ G, then τ(H) ≤ τ(G). -/theorem simple_graph_triangle_cover_number_mono {V : Type*} [Fintype V]    (G H : SimpleGraph V) (hle : H ≤ G) :    simple_graph_triangle_cover_number H ≤ simple_graph_triangle_cover_number G := by  classical  have hne : {n | ∃ F : Finset (Sym2 V), (∀ e ∈ F, e ∈ G.edgeSet) ∧      (∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t) ∧ F.card = n}.Nonempty := by    refine ⟨_, Finset.univ.filter (· ∈ G.edgeSet), ?_, ?_, rfl⟩    · intro e he      rw [Finset.mem_filter] at he      exact he.2    · intro t ht      obtain ⟨x, y, z, hxy, -, -, rfl⟩ := Finset.card_eq_three.1 ht.card_eq      have hadj : G.Adj x y := ht.isClique (by simp) (by simp) hxy      refine ⟨s(x, y), ?_, ?_⟩      · rw [Finset.mem_filter]        exact ⟨Finset.mem_univ _, hadj⟩      · intro v hv        simp only [Sym2.mem_iff] at hv        rcases hv with rfl | rfl <;> simp  obtain ⟨F, hFedge, hFcover, hFcard⟩ := Nat.sInf_mem hne  change F.card = simple_graph_triangle_cover_number G at hFcard  set F' : Finset (Sym2 V) := F.filter (· ∈ H.edgeSet)  have hF'edge : ∀ e ∈ F', e ∈ H.edgeSet := by    intro e he    rw [Finset.mem_filter] at he    exact he.2  have hF'cover : ∀ t : Finset V, H.IsNClique 3 t → ∃ e ∈ F', ∀ x ∈ e, x ∈ t := by    intro t ht    obtain ⟨e, heF, het⟩ := hFcover t (ht.mono hle)    induction' e using Sym2.ind with u v    have heG : G.Adj u v := hFedge s(u, v) heF    have hne : u ≠ v := G.ne_of_adj heG    have hu : u ∈ t := het u (by simp)    have hv : v ∈ t := het v (by simp)    have hadj : H.Adj u v := ht.isClique hu hv hne    refine ⟨s(u, v), ?_, het⟩    rw [Finset.mem_filter]    exact ⟨heF, hadj⟩  have hHle : simple_graph_triangle_cover_number H ≤ F'.card := by    apply Nat.sInf_le    exact ⟨F', hF'edge, hF'cover, rfl⟩  rw [← hFcard]  exact hHle.trans (Finset.card_filter_le _ _)
See it in the graphDiscuss this resultChallenge it