Observation 2: from a position of value every value is reachable in one move, and is not
ProvedArcKayles192.PSPACE.observation_2arc-kaylesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1sprague-grundy
Let be a simple graph and a position of Arc Kayles on it, with Sprague–Grundy value . Then
- for every there is a legal move (, ) with ;
- no legal move satisfies .
This is the mex property of the value function, used in Lemmas 3 and 4.
Differences from the source:
- encoding: a position is a graph; isolated vertices are removed automatically (p.3) → a position is a finite set S of remaining vertices of an ambient simple graph G, the current graph being G[S]; isolated vertices stay in S; reason: an isolated vertex carries no move, so outcomes and values are unchanged; every finite graph H is the position (H, all vertices), and every position is the finite graph G[S]
Preamble
import Mathlib import Definitions.Def_ArcKayles192_PSPACE_Game
Formal statement
namespace ArcKayles192.PSPACE
/-- **Observation 2** (p.2). From any position of value `n`, and for every `i < n`, there is a
move to a position of value `i`, but there is no move to a position of value `n`. -/
theorem observation_2 {V : Type*} [DecidableEq V] (G : SimpleGraph V) (S : Finset V) :
(∀ i < sg G S, ∃ u v, u ∈ S ∧ v ∈ S ∧ G.Adj u v ∧ sg G (S \ {u, v}) = i) ∧
(∀ u v, u ∈ S → v ∈ S → G.Adj u v → sg G (S \ {u, v}) ≠ sg G S) := by sorry
end ArcKayles192.PSPACE
Source
Édouard Bonnet, Arc Kayles is PSPACE-complete, STOC 2027 submission #192 (October 2026), source.pdf SHA-256 f8b3a1c14347452b03dab2f19656aa6d2b17ba3956fefe2abc190b98ce44fc53, p.2, Observation 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.