propm_cyclic_two_orientation
lemmaverified
For n at most 5, the cyclic orientation i -> i+1, i+2 of the complete graph covers every pair and has out-degree at most two.
Statement
lemma propm_cyclic_two_orientation (n : ℕ) (hn : n ≤ 5) : (∀ a b : Fin n, a ≠ b → cyclic_two_orientation n a b = true ∨ cyclic_two_orientation n b a = true) ∧ ∀ i : Fin n, (Finset.univ.filter fun j => cyclic_two_orientation n i j = true).card ≤ 2
- Source
- step towards propm_orientation_of_out_degree_two (PROPm orientations, arXiv:2602.18098 v2, Sec. 6)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cyclic_two_orientationThe orientation of the complete graph on n vertices with arcs i -> i+1 and i -> i+2 (mod n).
- Used by 1
- propm_orientation_exists_of_le_fiveEvery loopless multigraph on at most five agents with nonnegative additive valuations admits a PROPm orientation (with the PROPm slack…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The cyclic orientation `i → i+1, i+2 (mod n)` of `K_n` covers every pair and has out-degree at most two when `n ≤ 5`. -/lemma propm_cyclic_two_orientation (n : ℕ) (hn : n ≤ 5) : (∀ a b : Fin n, a ≠ b → cyclic_two_orientation n a b = true ∨ cyclic_two_orientation n b a = true) ∧ ∀ i : Fin n, (Finset.univ.filter fun j => cyclic_two_orientation n i j = true).card ≤ 2 := by interval_cases n <;> decide