(Aclaración) Un gráfico con un número par de vértices tiene dos vértices con un número par de vecinos comunes

Estoy relativamente poco familiarizado con las matemáticas y trato de estudiar por mi cuenta algunos temas de teoría de grafos. Ya encontré una prueba de esta afirmación en stackexchange (ver, por ejemplo, ∗∗Pruebe que cada gráfico con un número par de vértices tiene dos vértices con un número par de vecinos comunes ), y espero que mi pregunta sea específica suficiente para no ser un duplicado.

Así que aquí está el problema: tengo dificultades para entender exactamente cuándo la suposición de que$|V(G)|$es incluso juega su papel en la prueba . Creo que ya casi estoy, pero tengo la sensación de que me estoy equivocando en alguna parte. Entonces, esto es lo lejos que he llegado:

Probamos el enunciado por contradicción. Suponga que todos los pares de dos vértices en el gráfico tienen un número impar de vecinos comunes. Elige un vértice arbitrario$v\in V(G)$, y llamamos al subgrafo inducido por su vecindad$H$. Para todos$x,y\in V(H)$, si$\{x,y\}\in E(G)$, entonces$y$es vecino común de$v$y$x$en$G$. Así, el número de aristas en$H$es igual al número de vecinos comunes de un vértice en$H$tiene con$v$. Por suposición, este número es impar. Pero entonces, del lema del apretón de manos se deduce que hay un número par de vértices en$H$. Y así el grado de$v$incluso.

Ahora, considere el número de caminatas de longitud 2 a partir de$v$. Este número tiene que ser par. Para ver por qué, tenga en cuenta que cada caminata de este tipo consiste en el triple$(v,k,l)$, dónde$\{v,k\},\{k,l\}\in E(G)$(tenga en cuenta que$v$y$l$no son necesariamente vértices distintos). De la discusión anterior, sabemos que hay un número par de vértices adyacentes a$v$y que el grado de$k$es incluso así. De ello se deduce que el número de caminatas de longitud 2 a partir de$v$,$|W_{v,2}|$, se da como

Pero el número de caminatas de longitud 2 a partir de$v$es también la suma de los caminos de longitud 2 que comienzan con$v$y los ciclos de longitud-2 a partir de$v$. Este último es igual al grado de$v$, y por lo tanto es par. El número de caminos de longitud 2 a partir de$v$es igual al número de triples$(v,k,l)$dónde$\{v,k\},\{k,l\}\in E(G)$y$l\ne v$. Nótese que esto implica que$k$es vecino común de$l$y$v$, cuyo número es, por suposición, impar. Por lo tanto, el número de caminatas de longitud 2 a partir de$v$es

Parece que he llegado a una contradicción sin usar la suposición de que$|V(G)|$es uniforme, lo que me da una fuerte señal de que algo anda mal. Simplemente no puedo entender qué exactamente.