Demuestre que no puede existir un grafo G con vértices del grado dado

Question

Estoy trabajando en el libro titulado Introducción a la teoría de grafos por Gary Chartrand. Hay una pregunta que no puedo resolver. La pregunta es:

Demuestre que un gráfico G no puede existir con vértices de grado 1, 3, 3 y 3.

Puedo mostrarlo con una imagen, pero me gustaría formalizarlo con una prueba.

Gracias

Answer 1

Si el grafo no tiene bucles ni aristas múltiples, y existiera un grafo así, ¿qué implicaría después de eliminar el vértice de 1 valor y la arista unida a él?

Answer 2

Otra forma de pensar en ello es que cada uno de los vértices de grado tres debe ser adyacente a todos los demás vértices (suponiendo de nuevo que no haya bucles ni aristas múltiples). ¿Qué dice eso sobre el grado del vértice restante?

Answer 3

Otra forma de pensar en ello (sin bucles ni aristas múltiples) es ver que el grafo debe ser un subgrafo del grafo completo en cuatro vértices. Éste tiene seis aristas y el que quieres tendrá cinco (suma los grados y divide por dos). Intenta construir el grafo quitando una arista. Cuando quitas una arista de ese grafo afectas a dos vértices de los cuatro ...

Esto demuestra también que sólo hay un tipo de grafo con cuatro vértices y cinco aristas. Construir a partir de cero aristas no lo hace evidente.

Answer 4

Esto se puede demostrar de manera formal y sencilla mediante el Algoritmo Havel-Hakimi :

1. Ordenar la secuencia de grados en orden no creciente: 3,3,3,1.
2. Elimina el elemento más a la izquierda, el 3, y decrementa los 3 elementos siguientes en 1 para obtener la secuencia 2,2,0. Repitiendo este proceso, obtenemos la secuencia 1,-1 que obviamente no es gráfica.
3. Como la secuencia 1,-1 no es gráfica, por el Teorema de Havel-Hakimi, la secuencia original 3,3,3,1 tampoco es gráfica.