Gráfico coloreado con$2$ colores

Question

Llamemos a $G$ una gráfica con vértices en dos colores posibles. Si seleccionamos un vértice, cambiamos su color y cada vértice adyacente a él. ¿Es posible cambiar una gráfica de todo el primer color a todo el segundo usando tales movimientos?

No puedo encontrar ningún ejemplo contrario, pero tampoco puedo encontrar una prueba. ¿Qué piensas?

Answer 1

La respuesta es SÍ y los comentarios se dan varias referencias de este resultado llama la "iluminación de la lámpara del problema". A continuación hay una prueba directa.

Deje $G$ ser un grafo con vértices $v_1,v_2,\dots, v_n$ y deje $A$ ser una matriz tal que $a_{ij}=1$ si y sólo si $i=j$ o hay un borde entre el $v_i$ e $v_j$.

Suponga que los vértices de $G$ son de color azul (color $0$). Es posible cambiar su color a rojo (color de la $1$) mediante el uso de estos movimientos si y sólo si existe un vector $y=(y_1,\dots y_n)^t\in \mathbb{Z}_2^n$ tales que $$Ay=u$$ donde $u=(1,1,\dots,1)^t$, es decir, desde la matriz de $A$ es simétrica si y sólo si $$u\in \text{Im}(A)=\text{Im}(A^t)=(\text{Ker}(A))^{\perp}.$$ Por lo tanto, es suficiente para mostrar que $Ax=0$ implica $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}$$ y hemos terminado.

Answer 2

Sí, se puede hacer para cualquier gráfica. Este es un problema muy discutido llamado "problema del encendedor de la lámpara" o "el problema de todos" o "luces apagadas". Este documento que está disponible en línea parece una buena encuesta:
Rudolf Fleischer y Jiajin Yu, una encuesta del juego "Lights Out" .