digraph_apex_over_bidirected_complete
deforiginal
The digraph D_d on d + 2 vertices: a bidirected complete graph on the vertices 0, …, d, together with an apex d + 1 that sends an arc to every other vertex and receives none. It has no loops, minimum outdegree d and (d + 1)² arcs.
Statement
def digraph_apex_over_bidirected_complete (d : ℕ) : Digraph (Fin (d + 2))- Related work
- arXiv:2610.21381 (Optimally large cuts in both directions), Sec. 6 (the paper's example for d = 2: a bidirected triangle and a vertex sending edges to its three vertices); here for every d.
- Verified
- 16 Oct 2026
- Axioms
- none listed
- Used by 7
- digraph_apex_over_bidirected_complete_out_degreeEvery vertex of D_d has outdegree at least d.
- digraph_apex_over_bidirected_complete_two_has_bipartitionThere exists a vertex bipartition V = A ⊔ B of the apex digraph D₂ on 4 vertices such that both directed cut counts e(A, B) and e(B, A)…
- digraph_apex_over_bidirected_complete_three_has_bipartitionThere exists a vertex bipartition V = A ⊔ B of the apex digraph D₃ on 5 vertices such that both directed cut counts e(A, B) and e(B, A)…
- 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_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_apex_over_bidirected_complete_edge_countD_d has (d + 1)² arcs.
Lean source view module on GitHub
/-- Bidirected `K_{d+1}` on `0, …, d` plus an apex `d + 1` with arcs to all of them (no arcs into the apex). -/ def digraph_apex_over_bidirected_complete (d : ℕ) : Digraph (Fin (d + 2)) := { Adj := fun u v => u ≠ v ∧ v ≠ Fin.last (d + 1) }