Probar cada auto-complementarios gráfico con $4n+1$ vértices tiene al menos un vértice de grado $2n$

Question

Traté de demostrar mediante la inducción.

Caso Base $n=1$, $5$ los vértices. Me acaba de dibujar un pentágono, que ha $5$ vértices de grado $2$

Entonces puedo asumir para $n=k$,$4k+1$ vértices, hay al menos un vértice con grado de $2n$. El número de aristas de este gráfico es $\dfrac{(4k+1)(4k)}{4}=(4k+1)(k)$

A continuación, para $n=k+1$,$4k+5$ los vértices. El número de aristas es $\dfrac{(4k+5)(4k+4)}{4}=(4k+5)(k+1)$

El gráfico con $4k+1$ vértices tienen $8k+5$ más de los bordes de la gráfica con $4k$ vértices.

Aquí es donde me quedo atascado.Estoy en el camino correcto? ¿Cómo debo proceder?

Answer 1

El complementario gráfico a $G$ agrega todos los bordes que faltan en el grafo completo $K_{4n+1}$, y elimina todos los bordes. En $K_{4n+1}$ cada vértice ha $4n$ bordes, por lo que la complementación de los cambios en el proceso de cada grado de los vértices de$x$$4n-x$.

La auto-complementarios gráfico debe tener el mismo grado de secuencia como su complemento, y cada vértice tiene su grado de cambio de $\text{deg}(v)$ $4n{-}\text{deg}(v)$en el interruptor para el complemento - de ahí que también debe ser un vértice de grado en el gráfico original a cambiar de nuevo. Esto corresponde a la conmutación entre una posición inicial en el grado de secuencia y una tarde.

Así que en la posición media $2n{+}1$ en el grado de secuencia, debemos tener un vértice que cambia de valor con sí mismo; es decir, $\text{deg}(v) = 4n{-}\text{deg}(v)$. Lo que significa que por lo menos ese vértice, $\text{deg}(v) = 2n$.

---

Por otro lado, también podría considerar la posibilidad de que el otro $5$-vértice auto-complementarios gráfico (aparte de la $5$-ciclo) en cualquier prueba de que intente: (de http://mathworld.wolfram.com/Self-ComplementaryGraph.html):

Aquí $n=1$ del curso y la posición media de los grados de la secuencia es $3$ - y vemos la secuencia de $(3,3,\color{red}{2},1,1)$.

Answer 2

Deje $G$ ser un auto-complementarios gráfico de la orden de $4n+1$ y deje $\sigma:G\to\overline G$ ser un isomorfismo. Desde $G$ $\overline G$ tienen el mismo conjunto de vértices $V,$ $\sigma$ es una permutación de $V,$ un anti-automorphism de $G,$ asignación de los bordes de $G$ a los bordes de $\overline G$ y viceversa.

Considerar el ciclo de descomposición de la permutación $\sigma.$ (tenga en cuenta que estamos usando la palabra "ciclo" en el grupo de teoría de sentido, no de la teoría de grafos sentido!) Cada trivial ciclo de $\sigma$ deben ser de longitud, desde los bordes de $G$ se alternan con los bordes de las $\overline G$ a medida que vayamos por todo el ciclo. Desde $|V|$ es incluso, $\sigma$ debe tener un $1$-ciclo, es decir, de un punto fijo. (Es claro que el punto fijo es único, pero no es necesario).

Deje $v$ un punto fijo de $\sigma.$ Desde $\sigma$ es un isomorfismo entre el $G$ $\overline G,$ debemos tener $\deg_G(v)=deg_{\overline G}(v).$ Desde $\deg_G(v)+\deg_{\overline G}(v)=4n,$ se sigue que $\deg_G(v)=\deg_{\overline G}(v)=2n.$

P. S. también Es fácil ver que la longitud de un trivial ciclo de $\sigma$ no está solo, es un múltiplo de a $4;$ y si un vértice en un ciclo de grado $2n,$, a continuación, todos los vértices en este ciclo tienen un grado $2n.$ Desde $\sigma$ tiene un único punto fijo, se deduce que el número de vértices de grado $2n$ es congruente a $1$ modulo $4.$

Ejemplos. Hay dos auto-complementarios de gráficos de orden $5.$ Uno de ellos es $C_5,$ que tiene cinco vértices de grado $2;$ el otro es homeomórficos a la carta Una y tiene un vértice de grado $2.$