digraph_out_count
def
The out-degree of the vertex v of a digraph on Fin n.
Statement
def digraph_out_count {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (v : Fin n) : ℕ- Defined in
- arXiv:2610.25886 (Extremal arborescences in graph orientations), Conjecture 6.1; outdegrees
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 19
- regular_tournament_five_nearly_doubly_regularThe case k = 1 of the conjecture, in a stronger form: every regular tournament of order 5 is nearly doubly regular (any two distinct…
- tournament_cut_add_cut_compl_eq_sum_out_countIn any directed graph T on vertex set Fin n and for any subset S of vertices, the number of directed edges within S plus the number of…
- 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.
- tournament_exists_covering_realizationLet d be a realizable degree vector of an n-vertex tournament, and let v, w be vertices satisfying d v < d w. Then there exists a…
- digraph_out_laplacianThe out-degree Laplacian L_D of a digraph D on Fin n over ℝ: its diagonal entries are the out-degrees and its off-diagonal (i,j) entry is…
- tournament_near_regular_of_card_degreesIf a digraph on 2m vertices has exactly m vertices of out-degree m - 1 and exactly m vertices of out-degree m, then it is near-regular.
- tournament_universal_kings_iff_max_outdegreeFor every realizable degree vector d of an n-vertex tournament and every vertex v, v is a king in every tournament realizing d if and only…
- tournament_near_regular_card_degreesIn any near-regular tournament on 2m vertices with m ≥ 1, exactly m vertices have out-degree m - 1 and exactly m vertices have out-degree m.
- tournament_directed_cut_eq_of_outdegrees_eqLet T₁ and T₂ be tournaments on vertex set Fin n such that every vertex v has the same outdegree in T₁ and T₂. Then for every subset S ⊆…
- tournament_exists_covering_realization_of_realizesLet d be a degree vector on Fin n realized by a tournament T, and let v, w be vertices in Fin n satisfying d v < d w. Then there exists a…
- tournament_realizesA tournament T on Fin n realizes degree vector d if T is a tournament and the outdegree of every vertex i equals d i.
- exists_not_near_regular_tournament_fourThere exists a tournament on 4 vertices that is not near-regular.
- tournament_is_near_regularA tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m.
- tournament_not_near_regular_exists_arc_degree_gapIn a tournament on 2m vertices with m ≥ 2 that is not near-regular, there are vertices u, v with an arc u → v and out-degree of v at least…
- tournament_degree_vector_realizableA degree vector d on Fin n is realizable if there exists a tournament T on Fin n whose outdegrees are given by d.
- tournament_cut_count_eq_subIn any tournament T on vertex set Fin n and for any subset S of vertices, the directed cut size from S to its complement Sᶜ equals the sum…
- tournament_sum_out_countIn a tournament T on Fin n, the out-degrees sum to the number of unordered pairs: ∑_i d_i = n(n-1)/2.
- tournament_not_near_regular_exists_extreme_degreeIn any tournament on 2m vertices with m ≥ 1 that is not near-regular, there exists a vertex with out-degree ≥ m + 1 or out-degree ≤ m - 2.
- tournament_is_king_of_max_outdegreeIn every tournament on n vertices, every vertex of maximum outdegree is a king: every other vertex is reachable from it by a directed path…
Lean source view module on GitHub
/-- The out-degree of the vertex v of a digraph on Fin n. -/ def digraph_out_count {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (v : Fin n) : ℕ := (Finset.univ.filter (fun w => D.Adj v w)).card