# Colored graph with $2$ colors

Let us call $$G$$ a graph with vertices in two possible colours. If we select a vertex, we change the colour of it and of every vertex that is adjacent to it. Is it possible to change a graph from all the first colour to all the second using such moves?

I cannot find any counter example but either cannot find a proof. What do you think?

• When you say $G$ is "a graph with two coloured vertices", are you saying that just two of the vertices are coloured, or that every vertex is coloured with one of two colours? Nov 1, 2018 at 10:13
• There is a strategy to do it for each cycle graph by selecting each node once. Also, the order of selecting is not important for any graph. Maybe this is helpful? Nov 1, 2018 at 10:32
• It can be done for any graph. The general proof uses linear algebra. This is a famous problem, called the "lamp lighting problem" or the "lights out game" or the "all ones problem" and there is a lot of literature about it. For example this paper: arxiv.org/abs/math/0411201
– bof
Nov 1, 2018 at 10:32
• K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53.
– bof
Nov 1, 2018 at 10:36
• thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color Nov 1, 2018 at 12:21

Let $$G$$ be a graph with vertices $$v_1,v_2,\dots, v_n$$ and let $$A$$ be a matrix such that $$a_{ij}=1$$ if and only if $$i=j$$ or there is an edge between $$v_i$$ and $$v_j$$.
Assume that the vertices of $$G$$ are all blue (colour $$0$$). It is possible to change their colour to red (colour $$1$$) by using the those moves if and only if there is a vector $$y=(y_1,\dots y_n)^t\in \mathbb{Z}_2^n$$ such that $$Ay=u$$ where $$u=(1,1,\dots,1)^t$$, that is, since the matrix $$A$$ is symmetric, if and only if $$u\in \text{Im}(A)=\text{Im}(A^t)=(\text{Ker}(A))^{\perp}.$$ Thus it suffices to show that $$Ax=0$$ implies $$u\cdot x=0$$: \begin{align} 0&=\sum_{i=1}^n(Ax)_i=\sum_{i=1}^nx_i+\sum_{i=1}^n\sum_{j\not=i}a_{ij}x_j\\ &=u\cdot x+2\sum_{1\leq i and we are done.
• hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$\text{Im}(A^t)=(\text{Ker}(A))^{\perp}.$$ Nov 1, 2018 at 12:16
• Note that, $x\in \text{Ker}(A)$ iff $0=\langle Ax,y\rangle = \langle x, A^ty\rangle$ for all $y$. Nov 1, 2018 at 12:41