A counterexample to a lit-only sigma-game conjecture

A move in the sigma-game toggles the neighbors of a vertex; the lit-only game permits such a move only at a lit vertex. The gap for a graph is the largest difference, over starting configurations, between the minimum numbers of lights attainable in these two games. Goldwasser, Wang and Wu conjectured that a connected graph on $n$ vertices with gap greater than $n/2$ must be complete $m$-partite for $m\equiv3\pmod4$. We refute their Conjecture 5, published in 2011. The complement of the disjoint union of a six-cycle and an isolated vertex has a starting configuration reducible to zero lights by regular moves but to no fewer than four by lit-only moves. Its lit-only orbit has three configuration types. Replacing every vertex by $m$ independent copies gives connected graphs on $7m$ vertices that are not complete multipartite, with a uniform starting configuration having minimum light numbers $0$ and $4m$. The counterexample and this family are proved in Lean from the definitions.

Checked in Lean from the definitions; not yet reviewed by experts. Produced by AI models under the author's direction.