AFTD Auto-Formalizing Theoretical Domains

digraph_arborescence_count_through_sanity

theoremverified

through(D, a → b) vanishes when a → b is not an arc of D, never exceeds tau(D), and on the two-vertex complete digraph the arc 0 → 1 lies in exactly one arborescence.

Statement

theorem digraph_arborescence_count_through_sanity {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (a b : Fin n) :
    (a ≠ b → ¬ D.Adj a b → digraph_arborescence_count_through D a b = 0) ∧
    digraph_arborescence_count_through D a b ≤ digraph_arborescence_count D ∧
    @digraph_arborescence_count_through 2 ⊤ (fun _ _ => isTrue trivial) 0 1 = 1
Source
step towards tournament_not_near_regular_exists_improving_tournament
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The theorem establishes three sanity properties for the through-arc arborescence count through(D, a → b). First, when a ≠ b and a → b is not an arc in D, no arborescence can contain it: the root is a fixed point of the parent map (which would force a = b if a were the root), while any non-root vertex must map to an out-neighbor (which would force a → b to be an arc). Second, the through-arc count is bounded by the total arborescence count tau(D) because arborescences containing a given arc form a subset of all arborescences for each root. Third, on the complete digraph with two vertices, the through-arc count is verified to equal 1 by direct evaluation.

  1. The proof splits into three independent goals: vanishing on non-arcs, the upper bound by the total arborescence count, and the value on the two-vertex complete digraph.

    The statement is a conjunction of three claims. We split the goal into three separate parts, introducing for the first part the hypotheses that $a \neq b$ and that $a \to b$ is not an arc in $D$.

    line 6

      refine ⟨fun hab hAdj => ?_, ?_, ?_⟩
  2. Showing that the through-arc count is zero reduces to showing that no parent function satisfies the arborescence conditions at root $r$ while mapping $a$ to $b$.

    By definition, the through-arc count is the sum over all roots $r$ of the number of arborescences rooted at $r$ containing arc $a \to b$. By `Finset.sum_eq_zero`, a sum of natural numbers vanishes if every summand is zero. Each summand counts the elements of a filtered set of parent functions; by `Finset.card_eq_zero` and `Finset.filter_eq_empty_iff`, this count is zero precisely when no parent function satisfies all the conditions.

    lines 7–9

    uses Finset.sum_eq_zero, Finset.card_eq_zero, Finset.filter_eq_empty_iff

      · unfold digraph_arborescence_count_through
        refine Finset.sum_eq_zero (fun r _ => ?_)
        rw [digraph_arborescence_count_at_through, Finset.card_eq_zero, Finset.filter_eq_empty_iff]
  3. No arborescence rooted at $r$ can contain the arc $a \to b$.

    Suppose, for contradiction, that $p$ is an arborescence rooted at $r$ with $p(a) = b$. By `eq_or_ne`, either $a = r$ or $a \neq r$. If $a = r$, then $p(a) = p(r) = r = a$ because the root is a fixed point of $p$; since $p(a) = b$, this implies $a = b$, contradicting the assumption $a \neq b$. If $a \neq r$, then $a$ is not the root, so by the definition of an arborescence there must be an arc $a \to p(a)$ in $D$; since $p(a) = b$, this means $a \to b$ is an arc in $D$, contradicting the assumption that $a \to b$ is not an arc.

    lines 10–17

    uses eq_or_ne

        intro p _
        rintro ⟨hpr, hout, -, hpab⟩
        obtain rfl | har := eq_or_ne a r
        · rw [hpr] at hpab
          exact hab hpab
        · have := hout a har
          rw [hpab] at this
          exact hAdj this
  4. The inequality through(D, a → b) ≤ tau(D) reduces to showing that for each root $r$, the set of arborescences rooted at $r$ through $a \to b$ is a subset of all arborescences rooted at $r$.

    Both the through-arc count and the total arborescence count tau(D) are defined as sums over all roots $r$. By `Finset.sum_le_sum`, it suffices to show termwise inequality for each root $r$. Since each term is the cardinality of a finite set, `Finset.card_le_card` reduces the inequality of counts to set inclusion.

    lines 18–21

    uses Finset.sum_le_sum, Finset.card_le_card

      · unfold digraph_arborescence_count_through digraph_arborescence_count
        refine Finset.sum_le_sum (fun r _ => ?_)
        rw [digraph_arborescence_count_at_through, digraph_arborescence_count_at]
        refine Finset.card_le_card ?_
  5. For each root $r$, every arborescence through $a \to b$ is an arborescence rooted at $r$.

    Given any parent function $p$ in the filtered set for the through-arc count, we unpack set membership using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`. The through-arc condition requires $p(r) = r$, arc validity for all non-root vertices, convergence to $r$ in $n$ steps, and $p(a) = b$. Dropping the condition $p(a) = b$ leaves the defining conditions of an arborescence rooted at $r$.

    lines 22–24

    uses Finset.mem_filter, Finset.mem_univ, true_and

        intro p hp
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢
        exact ⟨hp.1, hp.2.1, hp.2.2.1⟩
  6. On the two-vertex complete digraph, the arc 0 → 1 lies in exactly one arborescence. automation

    On a fixed digraph with two vertices, the arborescence count is a finite computation, which is verified directly by computational evaluation.

    line 25

      · decide
Finset.sum_eq_zero
A finite sum of elements in an additive monoid is zero if every term is zero.
Finset.card_eq_zero
A finite set has cardinality zero if and only if it is empty.
Finset.filter_eq_empty_iff
Filtering a finite set by a predicate gives the empty set if and only if no element in the set satisfies the predicate.
eq_or_ne
For any two elements, either they are equal or they are not equal.
Finset.sum_le_sum
A sum over a finite set is bounded by another if each summand is bounded by the corresponding summand.
Finset.card_le_card
If a finite set is a subset of another, then its cardinality is less than or equal to the other's cardinality.
Finset.mem_filter
An element belongs to the filter of a finite set by a predicate if and only if it belongs to the set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and
The conjunction `True ∧ 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

/-- Sanity checks for the through-arc count: zero on a non-arc, bounded by tau(D), and equal to 1 on the complete digraph on two vertices. -/theorem digraph_arborescence_count_through_sanity {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (a b : Fin n) :    (a ≠ b → ¬ D.Adj a b → digraph_arborescence_count_through D a b = 0) ∧    digraph_arborescence_count_through D a b ≤ digraph_arborescence_count D ∧    @digraph_arborescence_count_through 2 ⊤ (fun _ _ => isTrue trivial) 0 1 = 1 := by  refine ⟨fun hab hAdj => ?_, ?_, ?_⟩  · unfold digraph_arborescence_count_through    refine Finset.sum_eq_zero (fun r _ => ?_)    rw [digraph_arborescence_count_at_through, Finset.card_eq_zero, Finset.filter_eq_empty_iff]    intro p _    rintro ⟨hpr, hout, -, hpab⟩    obtain rfl | har := eq_or_ne a r    · rw [hpr] at hpab      exact hab hpab    · have := hout a har      rw [hpab] at this      exact hAdj this  · unfold digraph_arborescence_count_through digraph_arborescence_count    refine Finset.sum_le_sum (fun r _ => ?_)    rw [digraph_arborescence_count_at_through, digraph_arborescence_count_at]    refine Finset.card_le_card ?_    intro p hp    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢    exact ⟨hp.1, hp.2.1, hp.2.2.1⟩  · decide
See it in the graphDiscuss this resultChallenge it