AFTD Auto-Formalizing Theoretical Domains

digraph_apex_over_bidirected_complete_edge_count

theoremverified

D_d has (d + 1)² arcs.

Statement

theorem digraph_apex_over_bidirected_complete_edge_count (d : ℕ)
    [DecidableRel (digraph_apex_over_bidirected_complete d).Adj] :
    digraph_edge_count (digraph_apex_over_bidirected_complete d) = (d + 1) ^ 2
Source
Lemma for digraph_min_cut_additive_bound_fails_for_every_d; arXiv:2610.21381 (Optimally large cuts in both directions), Sec. 6.
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The proof counts the arcs of the directed graph D_d by partitioning them by target vertex, so the total count is the sum of the in-degrees over all d + 2 vertices. By definition of the adjacency relation, no arcs point into the apex vertex Fin.last (d + 1), giving it in-degree 0, whereas every other vertex receives an arc from all d + 1 other vertices, giving it in-degree d + 1. Summing 0 for the apex and d + 1 for each of the remaining d + 1 vertices yields (d + 1) * (d + 1) = (d + 1)² arcs.

  1. The apex vertex has in-degree 0, while every other vertex has in-degree d + 1.

    For any vertex v in Fin (d + 2), we distinguish whether v is the apex vertex Fin.last (d + 1). If v is the apex, the adjacency condition requires the target to be distinct from the apex, so no arc can enter v; thus the set of in-neighbors is empty and has cardinality 0. If v is not the apex, an arc points from u to v if and only if u ≠ v, meaning the in-neighbors of v are exactly all other vertices, Finset.univ.erase v. The cardinality of this set is |Fin (d + 2)| - 1 = d + 2 - 1 = d + 1.

    lines 4–18

    uses Finset.card_eq_zero, Finset.filter_eq_empty_iff, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true, Finset.card_erase_of_mem, Finset.card_univ, Fintype.card_fin

      have hfib : ∀ v : Fin (d + 2),
          (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v).card =
            if v = Fin.last (d + 1) then 0 else d + 1 := by
        intro v
        split_ifs with hv
        · rw [Finset.card_eq_zero, Finset.filter_eq_empty_iff]
          intro u _ h
          exact h.2 hv
        · have : (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v) =
              Finset.univ.erase v := by
            ext u
            simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true]
            exact ⟨fun h => h.1, fun h => ⟨h, hv⟩⟩
          rw [this, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin]
          omega
  2. The number of arcs entering a vertex v equals the cardinality of the in-neighborhood of v.

    The projection map (u, w) ↦ u gives a bijection between the fiber of arcs whose target is v and the set of in-neighbors of v. Injectivity holds because both pairs have their second coordinate equal to v, and surjectivity holds because for any in-neighbor u of v, the pair (u, v) is an incoming arc.

    lines 19–35

    uses Finset.card_bij, Finset.mem_filter, Finset.mem_univ, true_and, Prod.ext

      have hbij : ∀ v : Fin (d + 2),
          ((Finset.univ.filter fun p : Fin (d + 2) × Fin (d + 2) =>
            (digraph_apex_over_bidirected_complete d).Adj p.1 p.2).filter (fun p => p.2 = v)).card =
          (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v).card := by
        intro v
        apply Finset.card_bij (fun p _ => p.1)
        · intro p hp
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢
          rw [← hp.2]
          exact hp.1
        · intro p hp q hq h
          simp only [Finset.mem_filter] at hp hq
          exact Prod.ext h (hp.2.trans hq.2.symm)
        · intro u hu
          refine ⟨(u, v), ?_, rfl⟩
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu ⊢
          exact ⟨hu, by simp⟩
  3. The total arc count equals the sum over all vertices v of their in-degrees.

    By definition, digraph_edge_count is the size of the set of all arcs. Partitioning this set by the second coordinate (the target vertex) via Finset.card_eq_sum_card_fiberwise expresses the total count as the sum of fiber sizes over all vertices. Rewriting using the fiber bijection and the in-degree formula turns this into the sum of 0 for the apex and d + 1 for all other vertices.

    lines 36–39

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ

      unfold digraph_edge_count
      rw [Finset.card_eq_sum_card_fiberwise (f := Prod.snd) (t := Finset.univ)
        (fun _ _ => Finset.mem_univ _)]
      simp only [hbij, hfib]
  4. Evaluating the sum of in-degrees gives (d + 2 - 1) * (d + 1).

    We isolate the apex term from the sum using Finset.add_sum_erase. The apex term evaluates to 0 and drops out. On the remaining set Finset.univ.erase (Fin.last (d + 1)), every vertex is distinct from the apex, so each summand is the constant d + 1. Summing this constant over the erased set yields its cardinality times d + 1, where the cardinality is |Fin (d + 2)| - 1 = d + 2 - 1.

    lines 40–42

    uses Finset.add_sum_erase, Finset.mem_univ, if_pos, zero_add, Finset.sum_congr, if_neg, Finset.ne_of_mem_erase, Finset.sum_const, Finset.card_erase_of_mem, Finset.card_univ, Fintype.card_fin, smul_eq_mul

      rw [← Finset.add_sum_erase _ _ (Finset.mem_univ (Fin.last (d + 1))), if_pos rfl, zero_add,
        Finset.sum_congr rfl (fun v hv => if_neg (Finset.ne_of_mem_erase hv)), Finset.sum_const,
        Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin, smul_eq_mul]
  5. The total arc count simplifies to (d + 1)².

    Linear arithmetic simplifies d + 2 - 1 to d + 1, leaving the expression (d + 1) * (d + 1). Commutative ring arithmetic then confirms this equals (d + 1)².

    lines 43–44

      rw [show d + 2 - 1 = d + 1 by omega]
      ring
and_true
The conjunction of a proposition with True simplifies to the proposition.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
Finset.add_sum_erase
A finite sum equals the term at a chosen element plus the sum over the set with that element removed.
Finset.card_bij
Two finite sets have equal cardinality if there exists a map between them that is injective and surjective.
Finset.card_erase_of_mem
Removing an element that belongs to a finite set decreases the set's cardinality by 1.
Finset.card_eq_zero
The cardinality of a finite set is 0 if and only if the set is empty.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set equals the sum over a target finite set of the cardinalities of its fibers under a map.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of the type.
Finset.filter_eq_empty_iff
Filtering a finite set by a predicate yields the empty set if and only if no element satisfies the predicate.
Finset.mem_erase
An element belongs to a set with a removed if and only if it is not equal to a and belongs to the original set.
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 its universal finset.
Finset.ne_of_mem_erase
Any element belonging to a set with a removed is distinct from a.
Finset.sum_congr
Two sums over finite sets are equal if their index sets are equal and their summands agree on every element.
Finset.sum_const
Summing a constant over a finite set equals the cardinality of the set multiplied by that constant.
if_neg
An if-then-else expression evaluates to the else-branch when the condition is false.
if_pos
An if-then-else expression evaluates to the then-branch when the condition is true.
Prod.ext
Two ordered pairs are equal if their first components are equal and their second components are equal.
smul_eq_mul
Scalar multiplication of natural numbers coincides with ordinary multiplication.
true_and
The conjunction of True with a proposition simplifies to the proposition.
zero_add
Adding zero on the left is the identity: 0 + a = a.

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 digraph_apex_over_bidirected_complete_edge_count (d : ℕ)    [DecidableRel (digraph_apex_over_bidirected_complete d).Adj] :    digraph_edge_count (digraph_apex_over_bidirected_complete d) = (d + 1) ^ 2 := by  have hfib : ∀ v : Fin (d + 2),      (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v).card =        if v = Fin.last (d + 1) then 0 else d + 1 := by    intro v    split_ifs with hv    · rw [Finset.card_eq_zero, Finset.filter_eq_empty_iff]      intro u _ h      exact h.2 hv    · have : (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v) =          Finset.univ.erase v := by        ext u        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true]        exact ⟨fun h => h.1, fun h => ⟨h, hv⟩⟩      rw [this, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin]      omega  have hbij : ∀ v : Fin (d + 2),      ((Finset.univ.filter fun p : Fin (d + 2) × Fin (d + 2) =>        (digraph_apex_over_bidirected_complete d).Adj p.1 p.2).filter (fun p => p.2 = v)).card =      (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v).card := by    intro v    apply Finset.card_bij (fun p _ => p.1)    · intro p hp      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢      rw [← hp.2]      exact hp.1    · intro p hp q hq h      simp only [Finset.mem_filter] at hp hq      exact Prod.ext h (hp.2.trans hq.2.symm)    · intro u hu      refine ⟨(u, v), ?_, rfl⟩      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu ⊢      exact ⟨hu, by simp⟩  unfold digraph_edge_count  rw [Finset.card_eq_sum_card_fiberwise (f := Prod.snd) (t := Finset.univ)    (fun _ _ => Finset.mem_univ _)]  simp only [hbij, hfib]  rw [← Finset.add_sum_erase _ _ (Finset.mem_univ (Fin.last (d + 1))), if_pos rfl, zero_add,    Finset.sum_congr rfl (fun v hv => if_neg (Finset.ne_of_mem_erase hv)), Finset.sum_const,    Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin, smul_eq_mul]  rw [show d + 2 - 1 = d + 1 by omega]  ring
See it in the graphDiscuss this resultChallenge it