AFTD Auto-Formalizing Theoretical Domains

simple_graph_card_vertices_le_edges_add_components

theoremverified

In any finite simple graph, the number of vertices is at most the number of edges plus the number of connected components.

Statement

theorem simple_graph_card_vertices_le_edges_add_components {V : Type*} [Fintype V]
    (G : SimpleGraph V) :
    Fintype.card V ≤ G.edgeFinset.card + Fintype.card G.ConnectedComponent
Source
Structural necessity and certificate-soundness helpers for the OP-306 campaign; arXiv:2610.22142, Sections 3.3.1 and 3.3.2. These make the optimal block-partition route an equivalence at every odd order; no new exact wild-number case or bound is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To prove that the number of vertices is at most the number of edges plus the number of connected components (|V| ≤ |E| + c), the proof decomposes the graph into its connected components. For each component C, the induced subgraph is connected, so its vertices and internal edges satisfy |V(C)| ≤ |E(C)| + 1. Summing this inequality over all components gives ∑ |V(C)| ≤ ∑ |E(C)| + c. Because the component vertex sets partition V, their sizes sum to |V|; and because each edge belongs to at most one component, the internal edge counts sum to at most |E|, yielding the desired bound.

  1. Define the vertex set A(C) and edge set E(C) for each connected component C of G.

    Working classically, define A(C) as the finset of vertices in the support of component C, and define E(C) as the finset of edges of G whose endpoints are both in A(C).

    lines 8–10

      classical
      let A (C : G.ConnectedComponent) : Finset V := C.supp.toFinset
      let E (C : G.ConnectedComponent) : Finset (Sym2 V) := G.edgeFinset.filter (fun e => e.toFinset ⊆ A C)
  2. The sum of the sizes of the vertex sets A(C) across all connected components equals the total number of vertices: ∑ C, |A(C)| = |V|.

    The canonical projection mapping each vertex to its connected component partitions V into fibers. By `Finset.card_eq_sum_card_fiberwise`, the total number of vertices equals the sum of the fiber sizes. Using `Set.mem_toFinset`, `SimpleGraph.ConnectedComponent.mem_supp_iff`, and `Finset.mem_filter`, each A(C) is identified with the fiber of vertices belonging to C. Rewriting the sum and applying `Finset.card_univ` establishes that ∑ C, |A(C)| = |V|.

    lines 11–20

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ, Set.mem_toFinset, SimpleGraph.ConnectedComponent.mem_supp_iff, Finset.mem_filter, true_and, Finset.card_univ

      have hsumV : (∑ C : G.ConnectedComponent, (A C).card) = Fintype.card V := by
        have hi := Finset.card_eq_sum_card_fiberwise (f := G.connectedComponentMk)
          (s := (Finset.univ : Finset V)) (t := (Finset.univ : Finset G.ConnectedComponent))
          (fun _ _ => Finset.mem_univ _)
        have hA : ∀ C : G.ConnectedComponent, A C = Finset.univ.filter (fun v => G.connectedComponentMk v = C) := by
          intro C
          ext v
          simp only [A,Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff,Finset.mem_filter,Finset.mem_univ,true_and]
        simp_rw [hA]
        simpa only [Finset.card_univ] using hi.symm
  3. For each connected component C, the number of vertices in C is at most the number of internal edges plus one: |A(C)| ≤ |E(C)| + 1.

    The induced subgraph on A(C) is identical to the subgraph induced on the support of C (via `Finset.mem_coe` and `Set.mem_toFinset`), which is connected by `C.connected_toSimpleGraph`. Any connected graph satisfies |V| ≤ |E| + 1 (`hconn.card_vert_le_card_edgeSet_add_one`). Using `Nat.card_eq_fintype_card`, `SimpleGraph.edgeFinset_card`, and `G.card_filter_edgeFinset_toFinset_subset`, the number of vertices and edges of the induced subgraph correspond to |A(C)| and |E(C)| respectively, yielding |A(C)| ≤ |E(C)| + 1.

    lines 21–35

    uses Finset.mem_coe, Set.mem_toFinset, C.connected_toSimpleGraph, hconn.card_vert_le_card_edgeSet_add_one, Nat.card_eq_fintype_card, SimpleGraph.edgeFinset_card, G.card_filter_edgeFinset_toFinset_subset

      have hc : ∀ C : G.ConnectedComponent, (A C).card ≤ (E C).card + 1 := by
        intro C
        have hset : (↑(A C) : Set V) = C.supp := by
          ext v
          simp only [A,Finset.mem_coe,Set.mem_toFinset]
        have hconn : (G.induce (↑(A C) : Set V)).Connected := by
          rw [hset]
          exact C.connected_toSimpleGraph
        have hi := hconn.card_vert_le_card_edgeSet_add_one
        have hv : Nat.card (↑(A C) : Set V) = (A C).card := by simp
        have he : Nat.card (G.induce (↑(A C) : Set V)).edgeSet = (E C).card := by
          rw [Nat.card_eq_fintype_card, ← SimpleGraph.edgeFinset_card]
          exact (G.card_filter_edgeFinset_toFinset_subset (A C)).symm
        rw [hv,he] at hi
        exact hi
  4. The sum of the edge counts across all components does not exceed the total number of edges in G: ∑ C, |E(C)| ≤ |G.edgeFinset|.

    Each cardinality |E(C)| is rewritten as a sum of indicator values over all edges using `Finset.card_eq_sum_ones` and `Finset.sum_filter`. Exchanging the order of summation with `Finset.sum_comm` expresses the total sum as ∑ e, ∑ C, [e ⊆ A(C)]. For any edge e, both of its endpoints can belong to at most one connected component: by `Finset.card_le_one`, if e is contained in both A(C) and A(D), taking an endpoint of e (via `Sym2.out_fst_mem` and `Sym2.mem_toFinset.2`) shows that the component containing this vertex is both C and D (using `Finset.mem_filter.1` and `Set.mem_toFinset`), so C = D. Therefore, the inner sum is at most 1 for each edge (`Finset.sum_le_sum`), giving ∑ C, |E(C)| ≤ |G.edgeFinset|.

    lines 36–55

    uses Finset.card_eq_sum_ones, Finset.sum_filter, Finset.sum_comm, Finset.sum_le_sum, Finset.card_le_one, Finset.mem_filter.1, Sym2.mem_toFinset.2, Sym2.out_fst_mem, Set.mem_toFinset

      have hsumE : (∑ C : G.ConnectedComponent, (E C).card) ≤ G.edgeFinset.card := by
        simp_rw [E,Finset.card_eq_sum_ones,Finset.sum_filter]
        rw [Finset.sum_comm]
        calc _ ≤ ∑ _e ∈ G.edgeFinset, 1 := by
              apply Finset.sum_le_sum
              intro e he
              rw [← Finset.sum_filter, ← Finset.card_eq_sum_ones]
              rw [Finset.card_le_one]
              intro C hC D hD
              have hc := (Finset.mem_filter.1 hC).2
              have hd := (Finset.mem_filter.1 hD).2
              have hv : e.out.1 ∈ e.toFinset := Sym2.mem_toFinset.2 (Sym2.out_fst_mem e)
              have hCv : G.connectedComponentMk e.out.1 = C := by
                have hi : e.out.1 ∈ C.supp := by simpa only [A,Set.mem_toFinset] using hc hv
                exact hi
              have hDv : G.connectedComponentMk e.out.1 = D := by
                have hi : e.out.1 ∈ D.supp := by simpa only [A,Set.mem_toFinset] using hd hv
                exact hi
              exact hCv.symm.trans hDv
          _ = _ := by simp
  5. The total number of vertices is at most the total number of edges plus the number of connected components: |V| ≤ |G.edgeFinset| + |G.ConnectedComponent|.

    Summing the component-wise inequality |A(C)| ≤ |E(C)| + 1 over all components C using `Finset.sum_le_sum` and distributing the sum with `Finset.sum_add_distrib`, the left-hand side is |V| (from the vertex sum) and the right-hand side simplifies to (∑ C, |E(C)|) + |G.ConnectedComponent| using `Finset.sum_const`, `Finset.card_univ`, `nsmul_eq_mul`, and `mul_one`. Finally, linear arithmetic (`omega`) combines this with ∑ C, |E(C)| ≤ |G.edgeFinset| to conclude |V| ≤ |G.edgeFinset| + |G.ConnectedComponent|.

    lines 56–60

    uses Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one

      have hi := Finset.sum_le_sum (fun C (_ : C ∈ (Finset.univ : Finset G.ConnectedComponent)) => hc C)
      rw [hsumV,Finset.sum_add_distrib] at hi
      simp only [Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_one] at hi
      have hi' : Fintype.card V ≤ (∑ C : G.ConnectedComponent, (E C).card) + Fintype.card G.ConnectedComponent := by exact_mod_cast hi
      omega
C.connected_toSimpleGraph
The subgraph induced on the support of a connected component C is connected.
Finset.card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over its elements.
Finset.card_eq_sum_card_fiberwise
For a map f from a finite set s into t, the cardinality of s equals the sum of the cardinalities of the fibers over elements of t.
Finset.card_le_one
A finite set has cardinality at most 1 if and only if any two of its elements are equal.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of the type.
Finset.mem_coe
Membership in a finset coerced to a set is equivalent to membership in the finset.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_filter.1
If an element belongs to a filtered finset, then it belongs to the base finset and satisfies the predicate (forward direction).
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.sum_add_distrib
The sum of a sum of functions over a finite set equals the sum of the individual sums.
Finset.sum_comm
A double sum over two finite sets can be computed by exchanging the order of summation.
Finset.sum_const
Summing a constant over a finite set equals the size of the set times the constant.
Finset.sum_filter
Summing a function over a filtered finset equals summing the indicator of the predicate times the function over the whole finset.
Finset.sum_le_sum
If one function is pointwise less than or equal to another over a finite set, its sum is less than or equal to the other's sum.
G.card_filter_edgeFinset_toFinset_subset
The number of edges with both endpoints in a subset s equals the number of edges of the induced subgraph on s.
hconn.card_vert_le_card_edgeSet_add_one
In any connected graph, the number of vertices is at most the number of edges plus one.
mul_one
Multiplying any element by 1 leaves it unchanged.
Nat.card_eq_fintype_card
For a finite type, its cardinality as an arbitrary type (Nat.card) equals its finite type cardinality (Fintype.card).
nsmul_eq_mul
Scalar multiplication of an element by a natural number equals ordinary multiplication by that number.
Set.mem_toFinset
An element belongs to the finset of a set if and only if it belongs to the set.
SimpleGraph.edgeFinset_card
The cardinality of the edge finset equals the cardinality of the edge set as a finite type.
SimpleGraph.ConnectedComponent.mem_supp_iff
A vertex belongs to the support of a connected component C if and only if its connected component is C.
Sym2.mem_toFinset.2
If a vertex is an endpoint of an unordered pair e, it belongs to the finset of vertices of e.
Sym2.out_fst_mem
The first endpoint of an unordered pair's representative belongs to the pair.
true_and
True and p is equivalent to p.

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 BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem simple_graph_card_vertices_le_edges_add_components {V : Type*} [Fintype V]    (G : SimpleGraph V) :    Fintype.card V ≤ G.edgeFinset.card + Fintype.card G.ConnectedComponent := by  classical  let A (C : G.ConnectedComponent) : Finset V := C.supp.toFinset  let E (C : G.ConnectedComponent) : Finset (Sym2 V) := G.edgeFinset.filter (fun e => e.toFinset ⊆ A C)  have hsumV : (∑ C : G.ConnectedComponent, (A C).card) = Fintype.card V := by    have hi := Finset.card_eq_sum_card_fiberwise (f := G.connectedComponentMk)      (s := (Finset.univ : Finset V)) (t := (Finset.univ : Finset G.ConnectedComponent))      (fun _ _ => Finset.mem_univ _)    have hA : ∀ C : G.ConnectedComponent, A C = Finset.univ.filter (fun v => G.connectedComponentMk v = C) := by      intro C      ext v      simp only [A,Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff,Finset.mem_filter,Finset.mem_univ,true_and]    simp_rw [hA]    simpa only [Finset.card_univ] using hi.symm  have hc : ∀ C : G.ConnectedComponent, (A C).card ≤ (E C).card + 1 := by    intro C    have hset : (↑(A C) : Set V) = C.supp := by      ext v      simp only [A,Finset.mem_coe,Set.mem_toFinset]    have hconn : (G.induce (↑(A C) : Set V)).Connected := by      rw [hset]      exact C.connected_toSimpleGraph    have hi := hconn.card_vert_le_card_edgeSet_add_one    have hv : Nat.card (↑(A C) : Set V) = (A C).card := by simp    have he : Nat.card (G.induce (↑(A C) : Set V)).edgeSet = (E C).card := by      rw [Nat.card_eq_fintype_card, ← SimpleGraph.edgeFinset_card]      exact (G.card_filter_edgeFinset_toFinset_subset (A C)).symm    rw [hv,he] at hi    exact hi  have hsumE : (∑ C : G.ConnectedComponent, (E C).card) ≤ G.edgeFinset.card := by    simp_rw [E,Finset.card_eq_sum_ones,Finset.sum_filter]    rw [Finset.sum_comm]    calc _ ≤ ∑ _e ∈ G.edgeFinset, 1 := by          apply Finset.sum_le_sum          intro e he          rw [← Finset.sum_filter, ← Finset.card_eq_sum_ones]          rw [Finset.card_le_one]          intro C hC D hD          have hc := (Finset.mem_filter.1 hC).2          have hd := (Finset.mem_filter.1 hD).2          have hv : e.out.1 ∈ e.toFinset := Sym2.mem_toFinset.2 (Sym2.out_fst_mem e)          have hCv : G.connectedComponentMk e.out.1 = C := by            have hi : e.out.1 ∈ C.supp := by simpa only [A,Set.mem_toFinset] using hc hv            exact hi          have hDv : G.connectedComponentMk e.out.1 = D := by            have hi : e.out.1 ∈ D.supp := by simpa only [A,Set.mem_toFinset] using hd hv            exact hi          exact hCv.symm.trans hDv      _ = _ := by simp  have hi := Finset.sum_le_sum (fun C (_ : C ∈ (Finset.univ : Finset G.ConnectedComponent)) => hc C)  rw [hsumV,Finset.sum_add_distrib] at hi  simp only [Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_one] at hi  have hi' : Fintype.card V ≤ (∑ C : G.ConnectedComponent, (E C).card) + Fintype.card G.ConnectedComponent := by exact_mod_cast hi  omega
See it in the graphDiscuss this resultChallenge it