AFTD Auto-Formalizing Theoretical Domains

arrows_markable_unmarked_empty

theoremverified

In the empty position the number of unmarked markable edges equals the number of markable (non-pendant) edges, tree_markable_edges.

Statement

theorem arrows_markable_unmarked_empty {V : Type*} [DecidableEq V] [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] :
    arrows_markable_unmarked G (ArrowsEmptyPos V) = tree_markable_edges G
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 3
  • 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…
  • tree_markable_edgesThe number of markable edges of a graph is the number of edges not incident to any leaf.
  • ArrowsEmptyPosThe empty starting position in ArrowsPos V whose boolean relation is everywhere false.
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

The theorem states that in the empty arrow game position, the number of unmarked markable edges equals the total number of markable edges. Both quantities are cardinalities of subsets of edges: the former requires edges to have no degree-1 endpoints and to be unmarked, while the latter only requires the degree condition. Since no edge is marked in the empty position, the unmarked condition is vacuously satisfied for every edge, so the two edge sets are identical and therefore have the same cardinality.

  1. It suffices to show that the set of unmarked markable edges in the empty position is identical to the set of all markable edges.

    We enable classical reasoning and unfold the definitions of `arrows_markable_unmarked` and `tree_markable_edges`. Both quantities are the cardinalities of filtered sets of edges: `tree_markable_edges` selects edges whose endpoints do not have degree 1, while `arrows_markable_unmarked` additionally requires the edge to be unmarked in the given position `ArrowsEmptyPos V`. Since two identical finite sets have equal cardinalities, applying congruence (`congr 1`) reduces the goal to proving that these two edge sets are equal.

    lines 4–6

      classical
      unfold arrows_markable_unmarked tree_markable_edges
      congr 1
  2. The two sets of edges are identical because no edge is marked in the empty position.

    By set extensionality (`ext e`), the two sets are equal if every edge $e$ belongs to the first if and only if it belongs to the second. By symmetric square induction (`Sym2.ind`), every edge $e$ can be represented as an unordered pair $s(a, b)$ of endpoints. By definition of `ArrowsEmptyPos`, all directed edges have value `false`, so the unmarked condition reduces to `false = false ∧ false = false`, which is identically true. Simplifying with this fact (`simp [ArrowsEmptyPos]`) reduces the conjunction to just the degree condition, establishing the equivalence.

    lines 7–9

    uses Sym2.ind

      ext e
      induction e using Sym2.ind with
      | _ a b => simp [ArrowsEmptyPos]
Sym2.ind
A property holds for all elements of the symmetric square Sym²(α) if it holds for every pair s(x, y).

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_empty {V : Type*} [DecidableEq V] [Fintype V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    arrows_markable_unmarked G (ArrowsEmptyPos V) = tree_markable_edges G := by  classical  unfold arrows_markable_unmarked tree_markable_edges  congr 1  ext e  induction e using Sym2.ind with  | _ a b => simp [ArrowsEmptyPos]
See it in the graphDiscuss this resultChallenge it