digraph_arborescence_count_at_through_root_eq_zero
The number of arborescences directed towards root r that use an arc starting at r is 0 whenever the target differs from r.
Statement
theorem digraph_arborescence_count_at_through_root_eq_zero {n : ℕ} (D : Digraph (Fin n))
[DecidableRel D.Adj] (r b : Fin n) (hrb : r ≠ b) :
digraph_arborescence_count_at_through D r r b = 0- Source
- step towards tournament_reverse_arc_arborescence_count_lt
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 count of arborescences directed towards root r that route through arc (r, b) is defined as the size of the set of parent functions p satisfying the in-arborescence conditions together with p(r) = b. By definition, any such function must fix the root (p(r) = r), while passing through (r, b) requires p(r) = b. Because r ≠ b, these two requirements contradict each other (r = p(r) = b), so the set of valid functions is empty and the count is zero.
To show that the count is zero, it suffices to show that no parent function satisfies the arborescence conditions rooted at r with p(r) = b.
Unfolding the definition of digraph_arborescence_count_at_through, the count is the cardinality of the set of functions p satisfying the in-arborescence conditions along with p(r) = b. A finite set has cardinality zero if and only if it is empty (Finset.card_eq_zero), which is equivalent to asserting that no function p belongs to the set (Finset.eq_empty_iff_forall_notMem).
uses
digraph_arborescence_count_at_through,Finset.card_eq_zero,Finset.eq_empty_iff_forall_notMemrw [digraph_arborescence_count_at_through, Finset.card_eq_zero] rw [Finset.eq_empty_iff_forall_notMem]
Assuming for contradiction that a function p belongs to this set, it must satisfy both p(r) = r and p(r) = b.
We introduce a function p and assume for contradiction that it belongs to the set. Simplifying membership in the filtered universal set (using Finset.mem_filter, Finset.mem_univ, and true_and), we obtain the conjunction of properties defining the set, which explicitly asserts both that p(r) = r (the root is a fixed point) and that p(r) = b (the outgoing arc from r leads to b).
uses
Finset.mem_filter,Finset.mem_univ,true_andintro p hp simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp
The conditions p(r) = r and p(r) = b contradict the hypothesis that r ≠ b.
From p(r) = r (giving r = p(r) by symmetry) and p(r) = b, equality transitivity implies r = b, which contradicts the hypothesis hrb : r ≠ b.
exact hrb (hp.1.symm.trans hp.2.2.2)
digraph_arborescence_count_at_through- the number of arborescences directed towards root r whose parent map sends vertex a to b is defined as the cardinality of the set of maps p satisfying p(r) = r, the valid arc condition, the path-to-root condition, and p(a) = b
Finset.card_eq_zero- a finite set has cardinality zero if and only if it is empty
Finset.eq_empty_iff_forall_notMem- a set is empty if and only if no element belongs to it
Finset.mem_filter- an element belongs to a filtered set if and only if it belongs to the base set and satisfies the filter predicate
Finset.mem_univ- every element of a finite type belongs to its universal set 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
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.
/-- An arborescence directed towards root r cannot use an outgoing arc from r. -/theorem digraph_arborescence_count_at_through_root_eq_zero {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (r b : Fin n) (hrb : r ≠ b) : digraph_arborescence_count_at_through D r r b = 0 := by rw [digraph_arborescence_count_at_through, Finset.card_eq_zero] rw [Finset.eq_empty_iff_forall_notMem] intro p hp simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp exact hrb (hp.1.symm.trans hp.2.2.2)