AFTD Auto-Formalizing Theoretical Domains

arrows_markable_unmarked_of_legal

theoremverified

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.

  1. 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.

    lines 4–6

    uses arrows_legal_move_degree_ne_one

      classical
      obtain ⟨u, v, hu, hq, -, hsu, hsv, -⟩ := h
      obtain ⟨hdu, hdv⟩ := arrows_legal_move_degree_ne_one G hu hq hsu hsv
  2. 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.

    lines 7–12

    uses Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk, Sym2.mem_iff.mp, propext, and_comm

      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
  3. 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.

    lines 13–14

    uses Finset.card_erase_add_one

      rw [← Finset.card_erase_add_one hmem]
      congr 2
  4. 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.

    lines 15–20

    uses Sym2.ind, Finset.mem_erase, Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk

      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
  5. 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.

    lines 21–26

    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_all
  6. Any 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.

    lines 27–30

    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.

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

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