simple_graph_star_forest_edgeSet_ncard
The star forest K_{1,n_1} ⊔ ... ⊔ K_{1,n_q} has ∑ n_i edges.
Statement
theorem simple_graph_star_forest_edgeSet_ncard (q : ℕ) (n : Fin q → ℕ) :
(simple_graph_star_forest q n).edgeSet.ncard = ∑ i, n i- Source
- helper for arXiv:2610.25958 (Size Ramsey numbers of star forests with two components on one side), Lemma 2.3 (PR-280)
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_star_forest_adj_iffAdjacency in the star forest: same component, one vertex the centre and the other a leaf.
- simple_graph_star_forestThe star forest K_{1,n_1} ⊔ ... ⊔ K_{1,n_q}: component i has a centre (i, none) adjacent to its n_i leaves (i, some j), and there are no…
- Used by 2
- simple_graph_size_ramsey_star_star_forest_edges_geLower bound of Lemma 2.3 of arXiv:2610.25958. Every finite graph G with G → (K_{1,p}, ⊔_i K_{1,n_i}) has at least ∑_i (p + n_i - 1) edges.
- simple_graph_size_ramsey_star_star_forest_arrowsUpper bound of Lemma 2.3 of arXiv:2610.25958. Some finite graph with ∑_i (p + n_i - 1) edges arrows (K_{1,p}, ⊔_i K_{1,n_i}): the disjoint…
The proof, explained
The star forest K_{1,n_1} ⊔ ... ⊔ K_{1,n_q} consists of q disjoint stars, where the i-th star has a central vertex and n_i leaves. The proof sets up a map φ identifying each leaf index (i, j) with the unique edge connecting that leaf to the center of star i. After showing that φ is injective and that its range is precisely the edge set, the number of edges equals the cardinality of the index set Σ_{i : Fin q} Fin (n_i), which evaluates to ∑ i, n_i.
Define an explicit map φ from the index set of leaves to unordered pairs of vertices.
Each star i has center ⟨i, none⟩ and leaves ⟨i, some j⟩ for j ∈ Fin (n i). We define φ(i, j) = s(⟨i, none⟩, ⟨i, some j⟩), which is the edge connecting leaf j of star i to the center of star i.
let φ : (Σ i : Fin q, Fin (n i)) → Sym2 (Σ i : Fin q, Option (Fin (n i))) := fun x => s(⟨x.1, none⟩, ⟨x.1, some x.2⟩)
The mapping φ is injective.
Assume φ(i, j) = φ(i', j'). By equality of unordered pairs (Sym2.eq_iff), either the centers and leaves match directly, or they match with endpoints swapped. The swapped case equates ⟨i, none⟩ with ⟨i', some j'⟩, which is impossible because applying isSome to the second component yields false = true (congrArg). In the direct case, equating the leaf components ⟨i, some j⟩ = ⟨i', some j'⟩ gives i = i' and some j = some j' (Sigma.mk.inj_iff, heq_eq_eq), hence j = j' by injectivity of some (Option.some.injEq).
uses
Sym2.eq_iff,Sigma.mk.inj_iff,heq_eq_eq,Option.some.injEq,congrArghave hφ : Function.Injective φ := by rintro ⟨i, j⟩ ⟨i', j'⟩ h simp only [φ, Sym2.eq_iff] at h rcases h with ⟨_, h2⟩ | ⟨h1, _⟩ · simp only [Sigma.mk.inj_iff] at h2 obtain ⟨rfl, h⟩ := h2 simp only [heq_eq_eq, Option.some.injEq] at h rw [h] · exact absurd (congrArg (fun x : (Σ i : Fin q, Option (Fin (n i))) => x.2.isSome) h1) (by simp)
Set up the characterization of the edge set as the range of φ by unpacking arbitrary vertex pairs.
By set extensionality, the edge set equals the range of φ if every edge candidate e is an edge if and only if it lies in the range of φ. Any element e of Sym2 is an unordered pair s(u, v) (Sym2.ind). Representing u as ⟨i, a⟩ and v as ⟨i', b⟩, we unfold the definition of edge set membership via adjacency (SimpleGraph.mem_edgeSet, simple_graph_star_forest_adj_iff) and set range (Set.mem_range).
uses
Sym2.ind,SimpleGraph.mem_edgeSet,simple_graph_star_forest_adj_iff,Set.mem_rangehave hrange : (simple_graph_star_forest q n).edgeSet = Set.range φ := by ext e induction e using Sym2.ind with | h u v => rcases u with ⟨i, a⟩ rcases v with ⟨i', b⟩ rw [SimpleGraph.mem_edgeSet, simple_graph_star_forest_adj_iff, Set.mem_range] constructor
Every edge of the star forest lies in the range of φ.
If s(⟨i, a⟩, ⟨i', b⟩) is an edge, then i = i' and exactly one endpoint is the center (none) while the other is a leaf (≠ none). If a = none and b ≠ none, then b = some b' (Option.ne_none_iff_exists'.mp), giving the edge as φ(i, b'). If b = none and a ≠ none, then a = some a', and by symmetry of unordered pairs (Sym2.eq_swap), the edge is s(⟨i, some a'⟩, ⟨i, none⟩) = φ(i, a'). In either case, the edge lies in the range of φ.
uses
Option.ne_none_iff_exists'.mp,Sym2.eq_swap· rintro ⟨hi, h⟩ simp only at hi subst hi rcases h with ⟨ha, hb⟩ | ⟨ha, hb⟩ · simp only at ha hb subst ha obtain ⟨b, rfl⟩ := Option.ne_none_iff_exists'.mp hb exact ⟨⟨i, b⟩, rfl⟩ · simp only at ha hb subst hb obtain ⟨a, rfl⟩ := Option.ne_none_iff_exists'.mp ha exact ⟨⟨i, a⟩, Sym2.eq_swap⟩Every element in the range of φ is an edge of the star forest.
An element in the range of φ has the form φ(j, c) = s(⟨j, none⟩, ⟨j, some c⟩). If this pair equals s(⟨i, a⟩, ⟨i', b⟩), then by Sym2.eq_iff either the endpoints match directly or they are swapped. In both cases, both endpoints share the star index j, and one is the center (none) while the other is a leaf (some c ≠ none), which satisfies the adjacency condition for the star forest (Or.inl, Or.inr).
uses
Sym2.eq_iff,Or.inl,Or.inr· rintro ⟨⟨j, c⟩, h⟩ simp only [φ, Sym2.eq_iff] at h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · cases h1 cases h2 exact ⟨rfl, Or.inl ⟨rfl, by simp⟩⟩ · cases h1 cases h2 exact ⟨rfl, Or.inr ⟨by simp, rfl⟩⟩The number of edges in the star forest is ∑ i, n i.
Since the edge set is the range of φ and φ is injective, the cardinality of the edge set equals the cardinality of the domain Σ i, Fin (n i) (Set.ncard_range_of_injective). We convert this to a finite type cardinality (Nat.card_eq_fintype_card), which evaluates on a sigma type as the sum of fiber cardinalities ∑ i, |Fin (n i)| (Fintype.card_sigma). Simplifying |Fin (n i)| = n i completes the proof.
uses
Set.ncard_range_of_injective,Nat.card_eq_fintype_card,Fintype.card_sigmarw [hrange, Set.ncard_range_of_injective hφ, Nat.card_eq_fintype_card, Fintype.card_sigma] simp
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if either x = z and y = w, or x = w and y = z.
Sigma.mk.inj_iff- Two dependent pairs ⟨a₁, b₁⟩ and ⟨a₂, b₂⟩ in a sigma type are equal if and only if a₁ = a₂ and b₁ is heterogeneously equal to b₂.
heq_eq_eq- Heterogeneous equality between terms of the same type is equivalent to standard equality.
Option.some.injEq- The Option.some constructor is injective: some x = some y if and only if x = y.
congrArg- Equality is preserved under function application: if a₁ = a₂, then f(a₁) = f(a₂).
Sym2.ind- Induction principle for unordered pairs: to prove a property of an unordered pair, it suffices to prove it for pairs of the form s(x, y).
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.
simple_graph_star_forest_adj_iff- Two vertices in the star forest are adjacent if and only if they belong to the same component and one is the star center (none) while the other is a leaf (some).
Set.mem_range- An element x belongs to the range of f if and only if there exists some y such that f(y) = x.
Option.ne_none_iff_exists'.mp- If an optional value is not none, it equals some x for some value x.
Sym2.eq_swap- Unordered pairs are symmetric: s(a, b) = s(b, a).
Or.inl- From a proof of A, infer the disjunction A ∨ B.
Or.inr- From a proof of B, infer the disjunction A ∨ B.
Set.ncard_range_of_injective- The cardinality of the range of an injective function equals the cardinality of its domain.
Nat.card_eq_fintype_card- For a finite type, the Nat.card cardinality coincides with the Fintype.card cardinality.
Fintype.card_sigma- The cardinality of a dependent sum Σ i, α i of finite types is the sum of the cardinalities of the fibers, ∑ i, |α i|.
- The graph formalization represents the star K_{1, n_i} using vertices of type Option (Fin (n_i)), where `none` represents the center of star i and `some j` represents leaf j.
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.
theorem simple_graph_star_forest_edgeSet_ncard (q : ℕ) (n : Fin q → ℕ) : (simple_graph_star_forest q n).edgeSet.ncard = ∑ i, n i := by let φ : (Σ i : Fin q, Fin (n i)) → Sym2 (Σ i : Fin q, Option (Fin (n i))) := fun x => s(⟨x.1, none⟩, ⟨x.1, some x.2⟩) have hφ : Function.Injective φ := by rintro ⟨i, j⟩ ⟨i', j'⟩ h simp only [φ, Sym2.eq_iff] at h rcases h with ⟨_, h2⟩ | ⟨h1, _⟩ · simp only [Sigma.mk.inj_iff] at h2 obtain ⟨rfl, h⟩ := h2 simp only [heq_eq_eq, Option.some.injEq] at h rw [h] · exact absurd (congrArg (fun x : (Σ i : Fin q, Option (Fin (n i))) => x.2.isSome) h1) (by simp) have hrange : (simple_graph_star_forest q n).edgeSet = Set.range φ := by ext e induction e using Sym2.ind with | h u v => rcases u with ⟨i, a⟩ rcases v with ⟨i', b⟩ rw [SimpleGraph.mem_edgeSet, simple_graph_star_forest_adj_iff, Set.mem_range] constructor · rintro ⟨hi, h⟩ simp only at hi subst hi rcases h with ⟨ha, hb⟩ | ⟨ha, hb⟩ · simp only at ha hb subst ha obtain ⟨b, rfl⟩ := Option.ne_none_iff_exists'.mp hb exact ⟨⟨i, b⟩, rfl⟩ · simp only at ha hb subst hb obtain ⟨a, rfl⟩ := Option.ne_none_iff_exists'.mp ha exact ⟨⟨i, a⟩, Sym2.eq_swap⟩ · rintro ⟨⟨j, c⟩, h⟩ simp only [φ, Sym2.eq_iff] at h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · cases h1 cases h2 exact ⟨rfl, Or.inl ⟨rfl, by simp⟩⟩ · cases h1 cases h2 exact ⟨rfl, Or.inr ⟨by simp, rfl⟩⟩ rw [hrange, Set.ncard_range_of_injective hφ, Nat.card_eq_fintype_card, Fintype.card_sigma] simp