Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a well-known game: We are given a finite undirected graph $G=(V,E)$ whose vertices are labeled by "0". At each turn, we pick a vertex, and then it and all its neighbors flip their label (0 becomes 1, 1 becomes 0). The goal is to reach a state where all labels are 1.

Although this is a known game, I don't know how it's called.

I know that the game is always solvable, regardless of the graph; I wish to know as many proofs to this fact as possible. I'm most interested in constructive proofs which are simple to program.

share|improve this question
2  
en.wikipedia.org/wiki/Lights_Out_(game) -- David Radcliffe had a nice write up of this somewhere, but I can't find it. A very related, perhaps equivalent game is called "chip firing" and you'll find lots of combinatorics papers talking about that, as it happens to give an algebraic structure to set of spanning trees of the graph. –  Jack Schmidt Jan 23 '12 at 16:34
add comment

1 Answer 1

up vote 4 down vote accepted

A constructive proof uses the following Lemma:

Lemma: If $G(V,E)$ is an undirected, connected, graph, the vertex set $V$ can be partitioned into two sets $V_1$ and $V_2$ such that in the two subgraphs induced by $V_1$ and $V_2$, the degree of each vertex is even.

To use this lemma to your problem, suppose $H$ is your given graph and suppose $H$ has at least one vertex of even degree. We add a new vertex $O$ and make it adjacent to each such vertex. If there is no vertex of even degree, we do nothing. Every vertex (except possibly $O$) is of odd degree in the new graph.

This new graph has a partition $V_1,V_2$ according to the above Lemma. Pick the partition which does not contain $O$ (say $V_1$) as your flipping set. Since any vertex in $V_1$ is incident to an even number of vertices in $V_1$, they flip, and since any vertex in $V_2$ (except possibly $O$) is incident to an odd number of vertices in $V_2$, they flip too.

The lemma has an inductive proof (which can be converted to an algorithm).

Proof of Lemma:

We proceed by induction on $|V|$. Bases cases are easy to verify.

Suppose $G(V,E)$ is an undirected connected graph with $|V| = n+1$.

If all vertices of $G$ are of even degree, we are done by taking $V_1 = V$ and $V_2 = \emptyset$

Suppose $v$ is a vertex with odd degree, whose neighbours are $v_1, v_2, \dots, v_k$.

Form a new graph $G'$ as follows:

If $v_i$ and $v_j$ are adjacent in $G$, delete the edge joining them. If $v_i$ and $v_j$ are not adjacent in $G$, add a new edge joining them.

Delete $v$.

Apply induction hypothesis to $G'$, say getting $V'_1$ and $V'_2$. One of $V'_1$, $V'_2$ must contain an even number of $v_i$, say $V'_1$.

It is easy to verify that the partition of $G$ we are looking for is $V_1 = V'_1 \cup \{v\}$ and $V_2 = V'_2$.

$\square$

The above inductive proof can be used to give an $\mathcal{O}(|V|^3)$ time algorithm, I believe. (Of course, the linear algebra way of solving this specific lights out might give the same). Perhaps a better/clever representation/way can make it sub-cubic.

There is also an elegant Linear algebra (existential) proof due to Noga Alon, which shows that the diagonal vector (making a vector out of the main diagonal) of an $nxn$ matrix $A$ over $\mathbb{F}_2$ is in its row space.

Both the proofs (the above writeup and the Linear Algebra Proof by Noga Alon) can be found in the book: "Combinatorial Problems and Exercises" by Laci Lovasz.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.