propm_mem_between
lemmaverified
Under an orientation, an edge incident to i that is held by another agent j lies in the parallel class of i and j.
Statement
lemma propm_mem_between {m n : ℕ} (ends : Fin m → Fin n × Fin n) (σ : Fin m → Fin n)
(hσ : is_orientation ends σ) {i j : Fin n} {e : Fin m} (he : e ∈ incident_edges ends i)
(hj : σ e = j) (hij : i ≠ j) : e ∈ edges_between ends i j- 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 3
- edges_betweenThe parallel class of edges joining agents i and j.
- incident_edgesThe relevant items E_i of agent i in a multigraph: the edges incident to i.
- is_orientationAn allocation of the edges of a multigraph is an orientation if every edge goes to one of its two endpoints.
- 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
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.
/-- Under an orientation, an edge at `i` held by `j ≠ i` lies in the parallel class `{i, j}`. -/lemma propm_mem_between {m n : ℕ} (ends : Fin m → Fin n × Fin n) (σ : Fin m → Fin n) (hσ : is_orientation ends σ) {i j : Fin n} {e : Fin m} (he : e ∈ incident_edges ends i) (hj : σ e = j) (hij : i ≠ j) : e ∈ edges_between ends i j := by simp only [incident_edges, edges_between, Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢ have ho := hσ e rw [hj] at ho generalize ends e = p at he ho ⊢ obtain ⟨a, b⟩ := p simp only [Prod.mk.injEq] at he ho ⊢ rcases he with rfl | rfl <;> rcases ho with rfl | rfl · exact absurd rfl hij · exact Or.inl ⟨rfl, rfl⟩ · exact Or.inr ⟨rfl, rfl⟩ · exact absurd rfl hij