arrows_markable_unmarked_empty
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.
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.
classical unfold arrows_markable_unmarked tree_markable_edges congr 1
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.
uses
Sym2.indext 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
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_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]