arrows_legal_move_degree_ne_one
If marking the unmarked edge uv as u -> v leaves u not a source and v not a sink, then neither u nor v has degree 1 (pendant edges can never be marked).
Statement
theorem arrows_legal_move_degree_ne_one {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {p q : ArrowsPos V} {u v : V} (hu : ArrowsUnmarked G p u v) (hq : ∀ x y, q.1 x y = if x = u ∧ y = v then true else p.1 x y) (hsu : ¬ ArrowsIsSource G q u) (hsv : ¬ ArrowsIsSink G q v) : G.degree u ≠ 1 ∧ G.degree v ≠ 1
- Source
- Helper for arrows_parity_of_threads_le_two, arXiv:2610.15145 Theorem 10.3 / Corollary 10.4 (the induction in the proof of Theorem 10.3: every option has value (e-1) mod 2 or an option of value e mod 2), done directly on positions of T without the sum decomposition
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- ArrowsUnmarkedIn a simple graph G and position p : ArrowsPos V, vertices u and v form an unmarked edge if G.Adj u v and both p.1 u v and p.1 v u are…
- ArrowsIsSourceIn a simple graph G and position p : ArrowsPos V, vertex u is a source if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1…
- ArrowsIsSinkIn a simple graph G and position p : ArrowsPos V, vertex u is a sink if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1 v…
- ArrowsPosGiven a type V, ArrowsPos V is the subtype of boolean-valued binary relations p : V → V → Bool that are asymmetric, meaning that for all…
- Used by 1
- arrows_markable_unmarked_of_legalEvery legal move of the Game of Arrows decreases the number of unmarked markable edges by exactly one.
The proof, explained
The proof proceeds by contradiction for each vertex separately. Marking the edge uv as u → v establishes that the directed edge from u to v is present in q. If u had degree 1, its unique neighbor would be v, meaning every incident edge points away from u, so u would be a source, contradicting the assumption. Symmetrically, if v had degree 1, its unique neighbor would be u, so the only incident edge points into v, making v a sink and contradicting the assumption.
In the updated orientation q, the directed edge from u to v is marked (q(u, v) = true).
By the definition of q given in hypothesis hq, the edge between x and y is directed from x to y if x = u and y = v, which immediately simplifies to true when evaluated at (u, v).
have hquv : q.1 u v = true := by rw [hq]; simp
It suffices to show G.degree u ≠ 1 and G.degree v ≠ 1 separately.
The goal is a conjunction of two inequalities, which is split into two independent subgoals.
constructorG.degree u ≠ 1
Suppose for contradiction that G.degree u = 1. We show that u must be a source in q, contradicting hypothesis hsu. A vertex with degree at least 1 is a source if all its incident edges are directed away from it. Since G.degree u = 1, its neighbor finset has cardinality 1 by SimpleGraph.card_neighborFinset_eq_degree, so by Finset.card_eq_one.mp this neighborhood is a singleton {a}. Because v is adjacent to u (from hu), v = a by Finset.mem_singleton. Any neighbor w of u must likewise satisfy w = a = v, so every outgoing edge from u is of the form (u, v). Since q(u, v) = true, every edge incident to u points away from u, making u a source and yielding the contradiction.
uses
Finset.card_eq_one.mp,SimpleGraph.card_neighborFinset_eq_degree,Finset.mem_singleton· intro h1 apply hsu refine ⟨by omega, fun w hw => ?_⟩ obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact h1 : (G.neighborFinset u).card = 1) have hv : v ∈ G.neighborFinset u := by simpa using hu.1 have hw' : w ∈ G.neighborFinset u := by simpa using hw rw [ha, Finset.mem_singleton] at hv hw' rw [hw', ← hv]; exact hquv
G.degree v ≠ 1
Suppose for contradiction that G.degree v = 1. We show that v must be a sink in q, contradicting hypothesis hsv. Symmetrically to the first case, G.degree v = 1 implies the neighbor finset of v has cardinality 1 by SimpleGraph.card_neighborFinset_eq_degree, so it is a singleton {a} by Finset.card_eq_one.mp. Since u is adjacent to v, u = a by Finset.mem_singleton. Thus any neighbor w of v satisfies w = u, meaning every edge incident to v is the edge from u to v. Since q(u, v) = true, every incident edge points into v, making v a sink and yielding the contradiction.
uses
Finset.card_eq_one.mp,SimpleGraph.card_neighborFinset_eq_degree,Finset.mem_singleton· intro h1 apply hsv refine ⟨by omega, fun w hw => ?_⟩ obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact h1 : (G.neighborFinset v).card = 1) have hv : u ∈ G.neighborFinset v := by simpa using hu.1.symm have hw' : w ∈ G.neighborFinset v := by simpa using hw rw [ha, Finset.mem_singleton] at hv hw' rw [hw', ← hv]; exact hquv
Finset.card_eq_one.mp- A finite set has cardinality 1 if and only if it is equal to a singleton set {a} for some element a (used here in the forward direction: cardinality 1 implies it is a singleton).
SimpleGraph.card_neighborFinset_eq_degree- For any vertex v in a graph G, the cardinality of its neighbor finset equals the degree of v.
Finset.mem_singleton- An element b belongs to the singleton finset {a} if and only if b = a.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
theorem arrows_legal_move_degree_ne_one {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {p q : ArrowsPos V} {u v : V} (hu : ArrowsUnmarked G p u v) (hq : ∀ x y, q.1 x y = if x = u ∧ y = v then true else p.1 x y) (hsu : ¬ ArrowsIsSource G q u) (hsv : ¬ ArrowsIsSink G q v) : G.degree u ≠ 1 ∧ G.degree v ≠ 1 := by have hquv : q.1 u v = true := by rw [hq]; simp constructor · intro h1 apply hsu refine ⟨by omega, fun w hw => ?_⟩ obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact h1 : (G.neighborFinset u).card = 1) have hv : v ∈ G.neighborFinset u := by simpa using hu.1 have hw' : w ∈ G.neighborFinset u := by simpa using hw rw [ha, Finset.mem_singleton] at hv hw' rw [hw', ← hv]; exact hquv · intro h1 apply hsv refine ⟨by omega, fun w hw => ?_⟩ obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact h1 : (G.neighborFinset v).card = 1) have hv : u ∈ G.neighborFinset v := by simpa using hu.1.symm have hw' : w ∈ G.neighborFinset v := by simpa using hw rw [ha, Finset.mem_singleton] at hv hw' rw [hw', ← hv]; exact hquv