Hay una razón por la que el número de no-isomorfo gráficos con $v=4$ es impar?

Question

Estoy trabajando a través de Trudeau Introducción a la Teoría de grafos, que contiene el siguiente problema:

En la siguiente tabla, los números de la segunda columna son en su mayoría aún. Si hacemos caso de la primera fila en el suelo que $v=1$ es un trivial de la situación en la que su singularidad es mediocre, que deja a $v=4$ como el único número de vértices mencionados para los cuales hay un número impar de gráficos. ¿Crees que esto es debido a la casualidad, o puede usted pensar en alguna razón por la $v=4$ debe ser único?

 v número de no-isomorfo gráficos
 1 1
 2 2
 3 4
 4 11
 5 34
 6 156
 7 1,044
 8 12,346
 9 308,708

Tenga en cuenta que este problema se refiere a la cantidad de no-isomorfo gráficos.

He aquí lo que tengo hasta ahora:

El máximo número de aristas de un grafo con a$v=4$$\max(e)=\frac{1}{2}(v)(v-1)=\frac{1}{2}(4)(3)=6$. Los gráficos con $e=0,1,2,4,5,6$ vienen en pares porque cada gráfico tiene un complemento. Por lo tanto, hay un número impar de gráficos con la $v=4$ fib hay un número impar de gráficos con la $v=4$$e= \frac{\max(e)}{2}$.

Hay 3 gráficos con $v=4$$e= \frac{\max(e)}{2}=3$, por lo tanto, hay un número impar de gráficos con la $v=4$.

Sin embargo, no entiendo por qué la $v=4$ debe ser especial en este sentido, incluso aunque no se siente especial.

Answer 1

Definición: Deje $g(n)$ denotar el número de etiqueta gráficos en $n$ vértices, vamos a $e(n)$ denotar su $2$-parte, que es la potencia más grande de $2$ que se divide $g(n)$.

Lema: Si $n\geq5$ es impar, a continuación,$e(n) = (n+1)/2-\lfloor \log_2(n) \rfloor$. Si $n \geq 4$ es incluso, a continuación, $e(n) \geq n/2 - \lfloor \log_2(n) \rfloor$ con igualdad de iff $n$ es una potencia de $2$.

Corolario: La cantidad de etiqueta gráficos, incluso por $n > 4$

Algunos de los valores de $e(\{4,5,\ldots,15\})=\{0,1,1,2,1,2,2,3,3,4,4,5\}$ (para los números es el límite inferior).

El teorema es debido a Steven C. Atender y Robert W. Robinson y puede ser encontrado, incluyendo una prueba, en esta publicación.

Se menciona que $g(n)$ no está solo, sino que contiene un gran número de $2$'s en su primer factorización de grandes $n$ (esto también se desprende de la fórmula). De hecho, incluso se muestran que son asintóticamente $n/2$ factores de $2$$g(n)$.

Answer 2

Si un gráfico en $n$ vértices ha $e$ bordes, a continuación, el número de aristas en su complemento es $$ \frac{n(n-1)}{2} - e. $$ Así que si si $n(n-1)/2$ es impar podemos dividir los gráficos de pares (gráfico,complemento), y, a continuación, el número de gráficos debe ser par. En particular, el de la paridad del número de isomorfismo clases de gráficos es igual a la paridad en el número de isomorfismo clases de auto-complementarios de gráficos. Al $n=4$, el camino es el único auto-complementarios gráfico y el número de clases de isomorfismo es impar. Claramente al $n=6$ o $n=7$ debe haber un número par de isomorfismo clases de auto-complementarios de gráficos.