Demostración de que una secuencia de grados es gráfica (Havel-Hakami)

Question

He estado pensando en este problema en particular y estoy perplejo.

Para todos $n g\geq 5$ , demuestre que existe un gráfico, $G = \langle V,E \rangle$ tal que todos los vértices de $V$ tienen grado de $4$ .

He intentado utilizar Havel-Hakami con una secuencia de grados de n-cuatro (es decir: $[4,4,4,4,4,4,\ldots]$ ), pero había demasiados casos. No se me ocurre nada más. ¿Alguna sugerencia o idea?

Answer 1

Intenta dibujar un diagrama físico de dicho gráfico (todos los vértices de grado (valencia) 4) en una hoja de papel. Ahora comprueba si puedes subdividir algunas aristas con nuevos vértices y ajustar todos estos nuevos vértices para que tengan grado 4. ¿Cuántos vértices nuevos has tenido que añadir? Así que ahora, ¿qué tendrías que hacer para garantizar que puedes encontrar una colección de grafos con todas las secuencias más largas de sólo 4? Este enfoque debería evitar demasiados casos.

Answer 2

Una secuencia de grados $\{d_1, \dots, d_n \}$ es gráfica si la suma de los grados de los vértices es par y $$ \sum_{i=1}^{r} d_i \leq r(r-1) + \sum_{i=r+1}^{n} \min(r, d_i)$$

para cada número entero $r \leq n-1$ . Así que $4r \leq r(r-1)+4(n-r)$ . Por tanto, existe un gráfico de orden $n \geq 5$ que tiene todos los vértices de grado $4$ .

Answer 3

En general, si $r$ es un número entero par tal que $r \geq 0$ , entonces para todos los $n > r$ existe un gráfico de orden $n$ cuyos vértices tienen grado $r$ . Esto se denomina $r$ -gráfico regular de orden $n$ .

Para demostrarlo, utilizamos los llamados gráficos de Harary.

Sin entrar en demasiados detalles técnicos: visualice el $n$ vértices del gráfico para que estén en una disposición circular, y piense en cada vértice como adyacente al $r/2$ vértices "por delante" de él y el $r/2$ vértices detrás de él. Entonces, cada vértice tiene grado $r$ .

Answer 4

Otra respuesta similar en espíritu a la de Joseph Malkevitch pero más sencilla (en mi opinión).

Prueba por inducción en $n$ . Para $n=5$ el gráfico es $K_5$ . Supongamos ahora que existe un grafo de 4 regularidades en $n-1 \ge 5$ vértices. Elige dos aristas que no incidan en el mismo vértice. (Es fácil ver que tales aristas existen ya que $n-1 \ge 5$ .) "Corta" estas dos aristas para hacer 4 aristas colgantes y conéctalas a un nuevo vértice (que ahora tiene grado 4).