has_out_degree_two_orientation
def
The simple graph underlying the multigraph has an orientation in which every vertex has out-degree at most two.
Statement
def has_out_degree_two_orientation {m n : ℕ} (ends : Fin m → Fin n × Fin n) : Prop
- Defined in
- Fair Orientations: Proportionality and Equitability, arXiv:2602.18098 v2, Sec. 2 (relevant items, proportional share PROP_i = sum_{e in E_i} v_i(e)/n_e); PROPm as introduced at IJCAI 2021, with the maximin value restricted to relevant items as PROPX is in Def. 2.2; formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
- none listed
- Used by 1
- propm_orientation_of_out_degree_twoIf the simple graph underlying a loopless multigraph has an orientation with every out-degree at most two, then for nonnegative additive…
Lean source view module on GitHub
/-- The simple graph underlying the multigraph `ends` has an orientation in which every vertex has out-degree at most two: a relation `T` (`T i j` meaning the arc `i → j`) covering every edge in at least one direction, with at most two out-neighbours per vertex. -/ def has_out_degree_two_orientation {m n : ℕ} (ends : Fin m → Fin n × Fin n) : Prop := ∃ T : Fin n → Fin n → Bool, (∀ e, T (ends e).1 (ends e).2 = true ∨ T (ends e).2 (ends e).1 = true) ∧ ∀ i, (Finset.univ.filter fun j => T i j = true).card ≤ 2