A game played on graphs by "flipping" the state of a vertex and its neighbors 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.
 A: 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.
