Sea G un grafo tal que para todo u, v ∈ V (G), u no es igual a v , |N (u) ∩ N (v )| es impar. Entonces demuestre que el número de vértices de G es impar

Question

Después de trabajar durante algún tiempo, he descubierto el siguiente curso de acción. (a partir de algunos casos de muestra en 4 y 5 vértices)

i) Quería demostrar que el gráfico no tenía ningún vértice de grado impar.

ii) Existe al menos un vértice adyacente a todos los demás vértices.

Si puedo hacer esto, entonces si n = |G|, (n-1) es par - por lo tanto, n es impar.

Mi amigo me dijo que considerando un vértice típico y sus vecinos y considerando el subgrafo inducido sobre él, ha podido demostrar la 1ª parte.

Así que ahora para demostrar la 2ª parte, estaba cosiderando un vértice de máximo grado y si no tiene la propiedad anterior quería derivar una contradicción.

Pero creo que estoy atascado.

¿Alguna sugerencia?

Answer 1

Ya has demostrado que cada vértice $v$ tiene grado par, ya que si tuviera grado impar, entonces mira su conjunto de vecinos con la estructura del subgrafo inducido, $H$ . H$$ tiene un número impar de vértices con cada vértice que tiene grado impar, lo cual es una contradicción.

Ahora, consideremos la matriz de adyacencia $A$ de $G,$ donde consideramos que un vértice es adyacente a sí mismo. Entonces la condición de $|N(u)\cap N(v)|$ ser impar se traduce en $A^2=F,$ donde $F$ es la matriz en la que cada entrada es 1. Como cada vértice de $A$ tiene grado par, tenemos la identidad $AF=F$ . Por lo tanto, $F^2=FA^2=F$ . La identidad $F^2=F$ significa exactamente que el número de vértices es impar. Esto completa la prueba.

Answer 2

Parece que Jacob se me ha adelantado por unos minutos, pero una prueba de teoría de grafos algebraica funciona bien, así que añadiré mi ligera variante.

Si $A$ es el $n \times n$ matriz de adyacencia del grafo, que suponemos no tiene vértices de grado impar, entonces sobre $Z_2$ la condición muestra que $A^2$ tiene 0s en la diagonal y 1s en el resto, es decir, que $A^2 = J - I$ .

Pero (de nuevo sobre $Z_2$ ) $J-I$ tiene rango $n$ si $n$ está en paz. Pero $A$ no tiene rango completo como $A j = 0$ donde $j$ es el vector todo-uno (porque el grafo no tiene vértices de grado impar), y por tanto tampoco puede $A^2$ .

Answer 3

He mostrado esto en http://www.mathlinks.ro/viewtopic.php?t=68109 . Un problema muy bonito.

Answer 4

Pero no es cierto, ¿verdad? El gráfico sin vértices satisface su propiedad de forma vacía y tiene un número par de vértices.

Answer 5

He probado más de aquí que la afirmación ii) se mantiene cuando hacemos la suposición más fuerte de que $|N(u) \cap N(v)|$ es exactamente $1$ por cada $u, v$ .

Es probable que la mayor parte del argumento no se generalice, pero al menos una parte sí lo hace. Esa parte es que si $G$ es un contraejemplo mínimo, entonces el gráfico del complemento es conectado. Demostraré esto por contradicción:

Dejemos que $X$ y $Y$ sea una partición de los vértices en dos partes no vacías, de forma que cada vértice de X esté conectado a cada vértice de Y. Si $X$ tiene un tamaño uniforme, entonces vemos que $Y$ tiene la misma propiedad $G$ tiene y es menor que $G$ Así que $Y$ tiene el tamaño de impar y $G$ tiene un número impar de vértices. Si $X$ tiene tamaño impar, entonces si colapsamos $X$ a un punto $x$ seguimos teniendo la propiedad de que $|N(u) \cap N(v)|$ es impar para $u, v$ en $Y$ y también para cualquier $u$ en $Y$ , $|N(x)\cap N(u)|$ es impar por su paso i), por lo que $Y\cup x$ satisface las mismas propiedades $G$ y contiene un vértice que está conectado a todo, por lo que $Y\cup x$ tiene tamaño impar, por lo que $G$ tiene tamaño impar.

Desgraciadamente, no veo ninguna relación obvia y agradable que deban satisfacer dos vértices no adyacentes en nuestro grafo $G$ ...