digraph_edge_count
def
The number m of edges (arcs) of a finite digraph G.
Statement
def digraph_edge_count {V : Type*} [Fintype V] (G : Digraph V) [DecidableRel G.Adj] : ℕ
- Defined in
- arXiv:2610.21381 (Optimally large cuts in both directions), Sec. 1 (m = |E(G)|; digraphs have no loops and at most one edge per ordered pair).
- Verified
- 16 Oct 2026
- Axioms
- none listed
- Used by 17
- digraph_apex_over_bidirected_complete_out_degreeEvery vertex of D_d has outdegree at least d.
- digraph_both_cuts_ge_ceil_div_six_of_high_indegreeCase 1 of the proof of Theorem 1.4: in a loopless digraph with m arcs, if a vertex z has in-degree at least m/3 + 1 and some set A₀ ∋ z…
- digraph_both_cuts_ge_ceil_div_six_of_casesIf a finite digraph G admits a vertex subset A with both directed cut counts e(A, Aᶜ) and e(Aᶜ, A) at least ⌈m/6⌉ whenever some vertex has…
- digraph_both_cuts_ge_ceil_div_six_of_two_partitionsIf two vertex partitions have combined crossing count at least m and combined absolute directed-cut imbalance at most m/3, one partition…
- digraph_abs_net_degree_le_third_of_indegree_ltUnder the low-indegree hypotheses of the target, every absolute net degree is at most one third of the total arc count.
- digraph_apex_over_bidirected_complete_three_max_min_cutFor d = 3 (m = 16 arcs), every bipartition of D_3 has a directed cut of size at most 4 = ⌈2m/10⌉, so the bound of Conjecture 6.1 of…
- digraph_ssat_le_of_semisaturatingIf H : Digraph (Fin n) is a host digraph on Fin n with DecidableRel H.Adj such that digraph_is_semisaturating H G holds, then digraph_ssat…
- digraph_edge_count_eq_sum_outdegreesThe number of arcs of a finite digraph equals the sum of its outdegrees.
- digraph_ssatFor a natural number n and a digraph G : Digraph V on vertex type V, digraph_ssat n G is the infimum of the set of all natural numbers k :…
- digraph_edge_count_eq_cut_addFor any vertex set A, the edges of a digraph split into those inside A, from A to its complement, from the complement to A, and inside the…
- digraph_min_cut_additive_bound_fails_for_every_dFor every d ≥ 2 there is a loopless digraph with minimum outdegree at least d and m = (d + 1)² arcs in which every vertex bipartition A ⊔…
- digraph_apex_over_bidirected_complete_min_cut_leFor every vertex set A of D_d, min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)²/4⌋.
- digraph_outdegree_three_mul_le_edge_countIn a finite loopless digraph of minimum outdegree at least two, three times any vertex outdegree is at most the total number of arcs.
- digraph_semisaturation_isolated_edge_boundIf G : Digraph V is a finite oriented digraph with DecidableEq V and DecidableRel G.Adj satisfying digraph_is_oriented G and…
- digraph_semisaturation_bounded_of_isolated_edgeLet G : Digraph V be a finite oriented digraph on vertex type V with DecidableEq V and DecidableRel G.Adj such that digraph_is_oriented G…
- digraph_apex_over_bidirected_complete_edge_countD_d has (d + 1)² arcs.
- digraph_edge_count_eq_sum_indegreesThe number of arcs of a finite digraph equals the sum of its indegrees.
Lean source view module on GitHub
/-- The number of arcs of a finite digraph (ordered pairs `(u, v)` with `G.Adj u v`). -/ def digraph_edge_count {V : Type*} [Fintype V] (G : Digraph V) [DecidableRel G.Adj] : ℕ := (Finset.univ.filter fun p : V × V => G.Adj p.1 p.2).card