AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it