La existencia de un auto-complementarios gráfico

Question

Mostrar que existe una auto-complementry gráfico de la orden de $ n $ si y sólo si $ n = 0$ o $ 1 \ (\mbox{mod } 4) $.

Mis pensamientos hasta el momento:

He probado la 'sólo si' la dirección.

Para el 'si' dirección, necesito mostrar que si $ n = 0$ o $ 1 \ (\mbox{mod } 4) $, entonces puedo construir un auto-complementarios gráfico. He empezado a centrándose en el caso de $ n = 0 \ (\mbox{mod } 4) $; en particular, he dibujado un gráfico en el caso n = 4 (una forma de Z). Pero yo estoy luchando para generalizar mi método para n = 8 y superior (de hecho, yo no he construido con éxito un auto-complementarios gráfico de la orden de 8). No estoy realmente seguro de lo que pienso acerca de esto; soy nuevo en la Teoría de grafos y así no he tenido mucha práctica aún. EDIT: he tenido un pensamiento adicional. El gráfico I construir debe tener exactamente $ \frac{n(n-1)}{4} $ bordes.

Prefiero sugerencias de respuestas completas, al menos hasta que yo pueda alcanzar la respuesta a mí mismo. Gracias por su ayuda!

Answer 1

Sugerencia:

Dado un auto complementario gráfico en $n$ vértices, a tratar de construir un auto-complementarios gráfico en $n+4$ vértices.

Elaboración de la sugerencia:

Dado un auto-complementarios gráfico de $G$ $n$ vértices, añadir 4 más vértices que forman ya una 'Z' gráfico (la auto-complementarios gráfico de $n=4$). Conectar los vértices de $G$ a algunos de los cuatro recién agregado vértices. Mostrar que el nuevo gráfico así formado, es un auto-complementarios gráfico en $n+4$ vértices.

Respuesta completa:

Conecte cada vértice de $G$ a dos de los vértices que son los más alejados de distancia en el que el n=4 gráfico (que es, básicamente, un camino, y se conecta todos los vértices de $G$ a los puntos finales de ese camino).

Esto funciona incluso cuando $G$ tiene un solo vértice.

Answer 2

Casi un spoiler sugerencia:

Cuando tuve que probar esto, he creado soluciones para los casos n=4 y n=5 y generalizado de las soluciones individuales de aquellos a los conjuntos de 4 miembros que deben formar un grafo completo entre sí) con el nodo extra "en medio" para el caso donde n=1(mod 4).

Como ya ha creado una solución para n=4, que son más de la mitad del camino.

Mis profesores de la prueba sólo se utilizan dos conjuntos (y medio nodo para n=1(mod 4)), sin embargo mi prueba se considera perfectamente aceptable.