Determinar si un gráfico existe conociendo el grado de sus vértices

Question

Problema : Existe un grafo con diez vértices cuyos grados son $9,8,8,8,6,5,4,4,2,2$

Respuesta : Falso.

Mi intento : Como sabemos que $2 | E | = \sum _ { v \in V } d ( v )$ , $$2\cdot 28 = 9+8\cdot3+6+5+4\cdot2+2\cdot2$$ Por lo tanto, $| E | = 28$ . Dado que no sabemos más sobre el grafo (puede no ser un árbol), ¿cómo puedo determinar que dicho grafo no existe?

Answer 1

Supongamos que es simple y sin bucles.

Si ese existe entonces si borramos el nodo con grado $9$ y sus aristas, obtendríamos un gráfico:

$$7,7,7,5,4,3,3,1,1$$

ahora si eliminamos el nodo de grado $7$ y bordes obtenemos

$$6,6,4,3,2,2,1,0\;\;\;\;{\rm or} \;\;\;\;\geq 6,?,?,?,?,?,0,0$$

La segunda situación es imposible ya que al menos un nodo de grado $0$ debe estar conectada con la primera con grado al menos 6.

Así que supongamos que la situación 1 es posible, entonces también lo es: $$5,3,2,1,1,0$$

pero esto es realmente imposible (ya que al menos un nodo de grado $0$ debe estar conectado con el primero con grado al menos 5).

Por lo tanto, dicho gráfico no existe.

Answer 2

La respuesta es FALSO.

Procedemos a la Teorema de Havel-Hakimi que determina si una secuencia de grados puede representar un gráfico simple.

Aplicando este teorema, observamos que la secuencia de grados original es gráfica si y sólo si la secuencia de grados dada por $\{7, 7, 7, 5, 4, 3, 3, 2, 1\}$ es gráfico. Podemos seguir reiterando para obtener las siguientes listas de grados:

$$\{6, 6, 4, 3, 2, 2, 1, 0\} \rightarrow \{5, 3, 2, 1, 1, 0, 0\} \rightarrow \{2, 1, 0, 0, 0, -1\}$$

Pero, la última lista de grados no es claramente gráfica: ¡tiene una arista con un grado negativo! Por tanto, la respuesta es falsa.