digraph_reverse_arc
abbrev
The digraph obtained from D by reversing the arc between u and v: the two vertices exchange which of them points to the other, and every other adjacency is untouched.
Statement
abbrev digraph_reverse_arc {n : ℕ} (D : Digraph (Fin n)) (u v : Fin n) : Digraph (Fin n)- Source
- step towards tournament_not_near_regular_exists_improving_tournament
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 8
- tournament_reverse_arc_through_root_endpoint_eqIn a tournament T with arc u → v, the number of arborescences rooted at v using u → v equals the number of arborescences of reverse(T, u,…
- tournament_reverse_arc_laplacian_diffReversing an arc u → v of a tournament updates the out-degree Laplacian by an explicit rank-one matrix (e_u + e_v)(e_v - e_u)^T.
- digraph_reverse_arc_adjReversing the arc between u and v: the pair (u,v) gets the adjacency that (v,u) had, and any other pair keeps its adjacency.
- digraph_arborescence_count_reverse_arc_add_throughReversing a single arc u → v of a tournament satisfies tau(T) + through(T', v → u) = tau(T') + through(T, u → v), so the gain in the…
- tournament_reverse_arc_through_lt_iff_arborescence_ltIn a tournament T with an arc u → v, the total through-count strictly increases upon reversing u → v if and only if the total number of…
- tournament_reverse_arc_is_tournamentIf T is a tournament with an arc u → v, reversing that arc gives another tournament.
- tournament_four_not_near_regular_exists_improvingThe m = 2 case of the target, settled by finite computation: a non-near-regular tournament on 4 vertices has at most 9 arborescences while…
- digraph_arborescence_count_at_reverse_arc_add_throughFor a tournament with an arc u → v and any root r, the number of arborescences towards r grows by exactly (through-count of v → u after…
Lean source view module on GitHub
/-- Reverse the single arc between u and v of a digraph. -/ abbrev digraph_reverse_arc {n : ℕ} (D : Digraph (Fin n)) (u v : Fin n) : Digraph (Fin n) := ⟨fun x y => if (x = u ∧ y = v) ∨ (x = v ∧ y = u) then D.Adj y x else D.Adj x y⟩