digraph_arborescence_count_through_sanity
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
- digraph_arborescence_count_throughthrough(D, a → b): the number of spanning arborescences of D, over all choices of root, that use the arc a → b.
- digraph_arborescence_counttau(D): the total number of arborescences of D, the sum of a_r(D) over all roots r.
- digraph_arborescence_count_ata_r(D): the number of spanning arborescences of D directed towards the root r. Each is recorded by its successor map p: p r = r, every…
- digraph_arborescence_count_at_throughthrough_r(D, a → b): the number of spanning arborescences of D directed towards the root r that use the arc a → b, i.e. whose successor…
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.
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$.
refine ⟨fun hab hAdj => ?_, ?_, ?_⟩
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.
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]
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.
uses
eq_or_neintro 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
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.
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 ?_
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$.
uses
Finset.mem_filter,Finset.mem_univ,true_andintro p hp simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢ exact ⟨hp.1, hp.2.1, hp.2.2.1⟩
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.
· 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`.
- The third goal (line 25) is verified entirely by the `decide` tactic via computational evaluation of the finite graph.
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.
/-- 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