6
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ 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? $\endgroup$
    – Theo Bendit
    Nov 1, 2018 at 10:13
  • 1
    $\begingroup$ 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? $\endgroup$
    – Stefan Hante
    Nov 1, 2018 at 10:32
  • 3
    $\begingroup$ 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 $\endgroup$
    – bof
    Nov 1, 2018 at 10:32
  • 1
    $\begingroup$ K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53. $\endgroup$
    – bof
    Nov 1, 2018 at 10:36
  • $\begingroup$ thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color $\endgroup$
    – Marine Galantin
    Nov 1, 2018 at 12:21

2 Answers 2

Reset to default
5
$\begingroup$

The answer is YES and the above comments give several references for this result called the "lamp lighting problem". Below there is a direct proof.

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<j\leq n}a_{ij}x_j= u\cdot x \pmod{2}. \end{align}$$ and we are done.

$\endgroup$
2
  • $\begingroup$ 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}.$$ $\endgroup$
    – Marine Galantin
    Nov 1, 2018 at 12:16
  • 1
    $\begingroup$ Note that, $x\in \text{Ker}(A)$ iff $0=\langle Ax,y\rangle = \langle x, A^ty\rangle$ for all $y$. $\endgroup$
    – Robert Z
    Nov 1, 2018 at 12:41
4
$\begingroup$

Yes, it can be done for any graph. This is a much-discussed problem called the "lamp lighter's problem" or the "all ones problem" or "lights out". This paper which is available online looks like a good survey:
Rudolf Fleischer and Jiajin Yu, A Survey of the Game "Lights Out".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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