Suponga que una gráfica simple tiene 18 aristas, 4 vértices de grado 3 y todas las demás de grado 4. ¿Cuántos vértices tiene la gráfica?

Un gráfico simple no tiene aristas conectadas desde un nodo a sí mismo, por lo que el total de los grados de todos los vértices involucrados será 2 * 18 = 36. El total de los grados de los vértices de grado 3 es 12, por lo que el total de los Los grados de los vértices de grado 4 deben ser 36 - 12 = 24. Debe haber 24/4 = 6 vértices de grado 4, lo que hace un total de 10 vértices en el gráfico.

Puede construir un gráfico de este tipo de la siguiente manera. Identifique los vértices con los números del 1 al 10. Haga las siguientes conexiones:
(1-2-3-4-5-6-7-8-9-10-1)
(2-4)
(7-9)
(1- 5-8-1)
(3-6-10-3) Los
vértices 2, 4, 7, 9 tendrán grado 3. El resto tendrá grado 4. (Hay muchas otras posibilidades).