A game played on graphs by "flipping" the state of a vertex and its neighbors

Solution 1:

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.