Hola
Demuestre que para todo grafo \( G \) existe \( W\subset V(G) \) tal que todo vertice en \( W \) tiene un numero par de vecinos en \( W \) y todo vertice en \( V(G)/W \) tiene un numero impar de vecinos en \( W. \)
Esto es un Teorema que en la bibliografía que he podido consultar se atribuye a Sutner. Aunque no tengo acceso al artículo al parecer está probado aquí:
Sutner, K. (1989). "
Linear cellular automata and the garden-of-eden". The Mathematical Intelligencer, 11, 49-53.
No he llegado a encontrar la demostración completa; si algunas ideas (esencialmente
aquí) que me permiten reconstruir una:
El problema se puede enfocar así. Sea \( A \) la matriz de adyacencia de un grafo, es decir, una matriz \( n\times n \) (siendo \( n \) el número de vértices) que en la posición \( i,j \) vale \( 1 \) si los vértices \( i,j \) están relacionados y cero otro caso.
Dado un subconjunto \( W \) de vértices podemos asignarle un vector columna \( x \), tal que \( x_i=1 \) si el vértice \( i \) está en \( W \) y cero en otro caso.
Tanto para el vector columna como para la matriz de adyacencia podemos suponer en lo sucesivo que trabajamos en el cuerpo \( \Bbb Z_2 \).
Entonces si consideramos el producto \( Ax \) es un vector columna que en su posición \( i \)-ésima:
- Vale \( 0 \) si el vértice \( i \) está unido con un número par de vértices de \( W \), es decir, si el vértice \( i \) tiene un número par de vecinos en \( W \).
- Vale \( 1 \) si el vértice \( j \) está unido con un número impar de vértices de \( W \), es decir, si el vértice \( i \) tiene un número impar de vecinos en \( W \).
Para que el conjunto \( W \) cumpla lo pedido, \( Ax \) tiene que valer \( 0 \) en las posiciones donde \( x \) vale \( 1 \) (es decir los vértices de \( W \) tienen que tener un número par de vecinos en \( W \)) y tiene que valer \( 1 \) en las posiciones donde \( x \) vale \( 0 \) (es decir los vértices de \( V(G)\setminus W \) tienen que tener un número impar de vecinos en \( W \)).
Esto equivale a que, si llamamos \( U \) al vector formado sólo por \( 1s \) se cumpla:
\( Ax=U-x \)
Equivalentemente:
\( (A+Id)x=U \)
Por tanto el problema así reformulado equivale a probar que:
dada una matriz simétrica \( B\in {\cal M}_{n\times n}(\Bbb Z_2) \) con unos en la diagonal, el sistema \( Bx=U \) con \( U=(1,1,\ldots,1)^t \) siempre tiene solución.Lo anterior equivale a que probar que el vector \( U \) está en el espacio imagen de la matriz \( B \).
Ahora dado que \( B \) es simétrica los espacios \( ker(B) \) e \( Im(B) \) son ortogonales suplementarios, es decir, \( Im(B)=ker(B)^\bot \).
Spoiler
La prueba es sencilla. Dado \( u\in Im(B) \) por definición \( u=Bv \) para algún \( v \). Ahora si tomamos \( w\in ker(B) \):
\( w^tu=w^tBv=v^tB^tw=v^tBw=v0=0 \) (usamos que \( B^t=B \) y que \( Bw=0 \)).
Por tanto \( u\in ker(B)^\bot \), es decir, \( Im(B)\subset Ker(B)^\bot \). Pero por la fórmula de las dimensiones \( dim(Im(B))=n-dim(ker(B))=dim(ker(B))^\bot \) y así \( Im(B)=ker(B)^\bot \)
Entonces para probar que \( U\in Im(B) \) basta probar que \( U=(1,1,\ldots,1)^t\in ker(B)^\bot \), es decir, que para todo \( v \) tal que \( Bv=0 \) se cumple que \( v^tU=0 \).
Dado que trabajamos en \( \Bbb Z_2 \) lo anterior equivale a probar que si \( Bv=0 \) entonces \( v \) tiene un número par de unos.
Veamos que esto es cierto por reducción al absurdo. Supongamos que \( v \) tienen un número impar de unos. Que \( Bv=0 \) quieres decir que en cada fila, en las posiciones donde \( v \) tiene unos, \( B \) tienen en total un número par de unos.
Dicho de otra manera si restringimos \( B \) a las filas y columnas donde \( v \) tiene unos, tenemos una matriz \( B' \) simétrica, con unos en la diagonal, de tamaño \( k\times k \) (con k impar) y que en cada fila tiene un número par de unos. Por tanto el número total de unos de la matriz ha de ser par. Pero eso es falso, porque por ser simétrica si tiene \( m \) unos por encima de la diagonal tiene también \( m \) unos debajo de ella; y en la diagonal tiene \( k \) unos. En total \( 2m+k \) unos; como \( k \) es impar tiene un número impar de unos: contradicción.
Saludos.
