arrows_markable_unmarked_of_legal
Every legal move of the Game of Arrows decreases the number of unmarked markable edges by exactly one.
Statement
theorem arrows_markable_unmarked_of_legal {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p q : ArrowsPos V) (h : ArrowsLegalMove G p q) : arrows_markable_unmarked G q + 1 = arrows_markable_unmarked G p
- 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 7
- arrows_markable_unmarkedThe number of unmarked markable edges of a position p of the Game of Arrows on G: edges of G neither of whose endpoints has degree 1 and…
- ArrowsLegalMoveIn a simple graph G, a transition from position p to q in ArrowsPos V is a legal move if there exist u, v with ArrowsUnmarked G p u v such…
- arrows_legal_move_degree_ne_oneIf 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…
- 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…
- 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…
- Used by 1
- arrows_parity_of_strategy_classLet T be a finite tree and S a class of positions of the Game of Arrows on T that contains the empty position, such that from every…
The proof, explained
A legal move in the Game of Arrows marks a previously unmarked edge {u, v} as a directed arrow from u to v without creating any sources or sinks at u or v. Because neither endpoint can have degree 1, the edge {u, v} was one of the unmarked markable edges before the move. Marking (u, v) leaves the status of every other edge unchanged and marks {u, v}, so the set of unmarked markable edges after the move is precisely the original set with {u, v} removed. By the cardinality formula for erasing an element from a finite set, the number of unmarked markable edges decreases by exactly one.
The legal move chooses an unmarked edge {u, v} whose endpoints both have degree different from 1 in G.
Unpacking the definition of a legal move yields vertices u and v such that {u, v} is unmarked in p, position q sets the directed edge (u, v) to true leaving all other arrows unchanged, and neither u nor v becomes a sink or source in q. The lemma `arrows_legal_move_degree_ne_one` then implies that neither u nor v has degree 1 in G.
uses
arrows_legal_move_degree_ne_oneclassical obtain ⟨u, v, hu, hq, -, hsu, hsv, -⟩ := h obtain ⟨hdu, hdv⟩ := arrows_legal_move_degree_ne_one G hu hq hsu hsv
The edge {u, v} is an unmarked markable edge in position p.
By definition, an edge is markable and unmarked if its endpoints have degree not equal to 1 in G and neither orientation is marked. Since u and v are adjacent, neither has degree 1, and the edge was unmarked in p, the undirected edge s(u, v) belongs to the set of unmarked markable edges in p.
uses
Finset.mem_filter,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Sym2.lift_mk,Sym2.mem_iff.mp,propext,and_communfold arrows_markable_unmarked have hmem : s(u, v) ∈ G.edgeFinset.filter (fun e => (∀ w ∈ e, G.degree w ≠ 1) ∧ e.lift ⟨fun a b => p.1 a b = false ∧ p.1 b a = false, fun _ _ => propext and_comm⟩) := by simp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk] refine ⟨hu.1, ?_, by simpa using hu.2.1, by simpa using hu.2.2⟩ intro w hw; rcases Sym2.mem_iff.mp hw with rfl | rfl <;> assumption
It suffices to show that the set of unmarked markable edges in q is the set in p with {u, v} erased.
Because {u, v} belongs to the set of unmarked markable edges in p, erasing it reduces the set's size by 1 (`Finset.card_erase_add_one`). Hence, proving the set in q equals the set in p minus {u, v} directly implies the cardinality equation.
uses
Finset.card_erase_add_onerw [← Finset.card_erase_add_one hmem] congr 2
The set equality reduces to showing that an arbitrary edge {a, b} is unmarked and markable in q if and only if it is distinct from {u, v} and was unmarked and markable in p.
By set extensionality and representing an arbitrary edge as an unordered pair s(a, b) via `Sym2.ind`, we unfold the filtering criteria and the update rule defining q, reducing the equality to a two-way logical equivalence.
uses
Sym2.ind,Finset.mem_erase,Finset.mem_filter,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Sym2.lift_mkext e induction e using Sym2.ind with | _ a b => simp only [Finset.mem_erase, Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk, hq] constructor
Any edge that is markable and unmarked in q is not {u, v} and was already markable and unmarked in p.
If {a, b} were equal to {u, v}, then either (a, b) = (u, v) or (b, a) = (u, v) by `Sym2.eq_iff.mp`. But in position q the directed arrow (u, v) is marked true, contradicting that {a, b} is unmarked in q. Since {a, b} ≠ {u, v}, neither directed edge between a and b was altered by the move, so it was already unmarked in p.
uses
Sym2.eq_iff.mp· rintro ⟨hab, hd, h1, h2⟩ refine ⟨?_, hab, hd, ?_, ?_⟩ · rintro hs rcases Sym2.eq_iff.mp hs with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ <;> simp_all · by_cases hc : a = u ∧ b = v <;> simp_all · by_cases hc : b = u ∧ a = v <;> simp_allAny markable unmarked edge in p other than {u, v} remains markable and unmarked in q.
Since {a, b} ≠ {u, v}, we have (a, b) ≠ (u, v) and (b, a) ≠ (u, v) (using `Sym2.eq_swap`). Thus the update from p to q leaves both directions of {a, b} unchanged, so it remains unmarked in q.
uses
Sym2.eq_swap· rintro ⟨hne, hab, hd, h1, h2⟩ have hn1 : ¬ (a = u ∧ b = v) := by rintro ⟨rfl, rfl⟩; exact hne rfl have hn2 : ¬ (b = u ∧ a = v) := by rintro ⟨rfl, rfl⟩; exact hne Sym2.eq_swap refine ⟨hab, hd, ?_, ?_⟩ <;> simp [hn1, hn2, h1, h2]
arrows_legal_move_degree_ne_one- In a legal move marking directed edge (u, v) from position p to q such that u does not become a source and v does not become a sink in q, neither u nor v has degree 1 in G.
and_comm- Logical conjunction is commutative: a ∧ b ↔ b ∧ a.
Finset.card_erase_add_one- Erasing an element from a finite set decreases its size by 1: |s \ {a}| + 1 = |s| provided a ∈ s.
Finset.mem_erase- An element belongs to s \ {a} if and only if it is in s and distinct from a.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies predicate p.
propext- Two propositions that are logically equivalent are equal.
SimpleGraph.mem_edgeFinset- An edge belongs to the edge finset of a graph if and only if it is in its edge set.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) is in the edge set of a simple graph if and only if v and w are adjacent.
Sym2.eq_iff.mp- Two unordered pairs s(a, b) and s(u, v) are equal if and only if (a = u ∧ b = v) or (a = v ∧ b = u).
Sym2.eq_swap- The unordered pair s(a, b) is equal to s(b, a).
Sym2.ind- To prove a statement for all unordered pairs in Sym2 α, it suffices to prove it for pairs of the form s(x, y).
Sym2.lift_mk- Evaluating a symmetric function lifted to Sym2 on a pair s(a, b) yields the underlying function applied to (a, b).
Sym2.mem_iff.mp- If a vertex belongs to the unordered pair s(u, v), it equals either u or v.
- In Lean, undirected edges of a simple graph are formalized as elements of the quotient type `Sym2 V`, requiring explicit handling of pair symmetry and quotient lifting (`Sym2.ind`, `Sym2.lift_mk`, `Sym2.eq_iff.mp`, `Sym2.eq_swap`) that is taken for granted on paper.
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_markable_unmarked_of_legal {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p q : ArrowsPos V) (h : ArrowsLegalMove G p q) : arrows_markable_unmarked G q + 1 = arrows_markable_unmarked G p := by classical obtain ⟨u, v, hu, hq, -, hsu, hsv, -⟩ := h obtain ⟨hdu, hdv⟩ := arrows_legal_move_degree_ne_one G hu hq hsu hsv unfold arrows_markable_unmarked have hmem : s(u, v) ∈ G.edgeFinset.filter (fun e => (∀ w ∈ e, G.degree w ≠ 1) ∧ e.lift ⟨fun a b => p.1 a b = false ∧ p.1 b a = false, fun _ _ => propext and_comm⟩) := by simp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk] refine ⟨hu.1, ?_, by simpa using hu.2.1, by simpa using hu.2.2⟩ intro w hw; rcases Sym2.mem_iff.mp hw with rfl | rfl <;> assumption rw [← Finset.card_erase_add_one hmem] congr 2 ext e induction e using Sym2.ind with | _ a b => simp only [Finset.mem_erase, Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk, hq] constructor · rintro ⟨hab, hd, h1, h2⟩ refine ⟨?_, hab, hd, ?_, ?_⟩ · rintro hs rcases Sym2.eq_iff.mp hs with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ <;> simp_all · by_cases hc : a = u ∧ b = v <;> simp_all · by_cases hc : b = u ∧ a = v <;> simp_all · rintro ⟨hne, hab, hd, h1, h2⟩ have hn1 : ¬ (a = u ∧ b = v) := by rintro ⟨rfl, rfl⟩; exact hne rfl have hn2 : ¬ (b = u ∧ a = v) := by rintro ⟨rfl, rfl⟩; exact hne Sym2.eq_swap refine ⟨hab, hd, ?_, ?_⟩ <;> simp [hn1, hn2, h1, h2]