AFTD Auto-Formalizing Theoretical Domains

simple_graph_star_forest_edgeSet_ncard

theoremverified

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

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.

  1. 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.

    lines 3–4

      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⟩)
  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).

    lines 5–13

    uses Sym2.eq_iff, Sigma.mk.inj_iff, heq_eq_eq, Option.some.injEq, congrArg

      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)
  3. 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).

    lines 14–21

    uses Sym2.ind, SimpleGraph.mem_edgeSet, simple_graph_star_forest_adj_iff, Set.mem_range

      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
  4. 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 φ.

    lines 22–33

    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⟩
  5. 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).

    lines 34–42

    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⟩⟩
  6. 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.

    lines 43–44

    uses Set.ncard_range_of_injective, Nat.card_eq_fintype_card, Fintype.card_sigma

      rw [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|.

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

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
See it in the graphDiscuss this resultChallenge it