simple_graph_card_vertices_le_edges_add_components
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
- wild_odd_optimal_color_connecting_partitionAt odd order n>=3, every color-connecting edge set of size n-floor(n/3) in a proper complete-graph edge coloring yields a rooted partition…
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.
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).
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)
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|.
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_univhave 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
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.
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_subsethave 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
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|.
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_toFinsethave 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
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|.
uses
Finset.sum_le_sum,Finset.sum_add_distrib,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_onehave 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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