Necesito ayuda con esta prueba gráfica por favor

Question

Dejemos que $G$ sea un gráfico autocomplementario en el que $n = 4k+1$ . Demostrar que existe un número impar de vértices de grado $(n-1)/2$ .

No sé ni por dónde empezar con esto. Realmente necesito ayuda.

Gracias.

Answer 1

Como es isomorfo a su complemento podemos decir que

$$\sum_{i=1}^n deg(v_i)=\sum_{i=1}^n 4k-deg(v_i) $$

Entonces tenemos $$2\sum_{i=1}^n deg(v_i)=\sum_{i=1}^n 4k=4k(4k+1) $$

$$\sum_{i=1}^n deg(v_i)=2k(4k+1)$$

Tenga en cuenta que si $r=deg(v_i)$ entonces $4k-r$ es también un grado de otro vértice. Y si $r\neq 2k$ está claro que es otro vértice. Establece $s$ es el número de vértices con grado $2k$ y $l$ sea el número de vértices de grado inferior a $2k$ .

$$s2k+l(4k-r+r)=2k(4k+1)$$ $$s+2l=4k+1$$ $$s\equiv1 \text{ } mod(2)$$

Answer 2

Una pista: $v$ tiene grado $\frac{n-1}{2}$ en $G$ si y sólo si $v$ tiene grado $\frac{n-1}{2}$ en su complemento...

¿Puedes emparejar los vértices que no tienen grado $\frac{n-1}{2}$ ?

Answer 3

Si $E$ denota el conjunto de aristas de $G$ entonces $|E| = \frac{1}{2}\binom{|G|}{2}$ en un gráfico complementario (ya que la unión de los conjuntos de aristas de un gráfico y su complemento da el conjunto de aristas del gráfico completo en $|G|$ vértices). Por lo tanto, ya que $|G| = 4k+1$ , usted tiene $|E| = k(4k+1)$ . Además, si un vértice tiene grado $m \leq \left\lfloor\frac{n-2}{2}\right\rfloor$ en el gráfico, tiene grado $n-m-1$ en el complemento del gráfico (ya que cada vértice tiene $n-1$ vecinos en el gráfico completo), por lo que necesariamente, tenemos una biyección entre el conjunto de vértices de grado $m$ y de grado $n-m-1$ en un gráfico autocomplementario (cuando el grado es $(n-1)/2$ Sin embargo, no existe un procedimiento de emparejamiento de elementos como el anterior). Escribe $N_m$ para denotar el número de vértices de grado $m$ . Entonces tenemos (al contar los grados se sobrepasan las aristas dos veces) \begin{equation*} 2k(4k+1) = \sum_{v \in G} \deg(v) = 2kN_{(n-1)/2)} + 4k\sum_{m \leq (n-2)/2} N_m. \end{equation*} Para $k \geq 1$ dividir por $2k$ para conseguir $4k+1 = N_{(n-1)/2} + 2\sum_{m \leq (n-2)/2}N_m$ . Reduciendo mod 2, vemos que $N_{(n-1)/2}$ tiene que ser impar.