Gráfico con vértices que tienen determinados grados

Question

Dejemos que $G$ sea un gráfico simple con $n$ vértices, tal que $G$ tiene exactamente $7$ vértices de grado $7$ y el resto $n-7$ vértices de grado $5$ . ¿Cuál es el valor mínimo posible para $n$ ?

He conseguido que $n$ podría ser igual a $14$ con $G$ como el siguiente gráfico:

i) $G=G_1 \cup G_2$

ii) $|G_1|=|G_2|=7$

iii) $G_1 \cong K_7$

iv) cada vértice en $G_2$ está conectado a un vértice distinto en $G_1$ y cuatro más en $G_2$ (sujeto a las restricciones)

¿Cómo sé que este es el menor valor de $n$ ? Si no es así, ¿cómo puedo calcular el valor mínimo? Gracias.

Answer 1

Debemos tener un número impar de $5$ -vértices de grado para satisfacer la Lema del apretón de manos .

Podemos excluir la posibilidad de una secuencia de grados $(7,7,7,7,7,7,7,5)$ ya que cada $7$ -debe estar unido al vértice de grado $5$ -vértice de grado, dando una contradicción.

Un gráfico con secuencia de grados $(7,7,7,7,7,7,7,5,5,5)$ se ilustra a continuación:

Así que el mínimo $n$ -valor es $10$ .

Answer 2

Suponiendo que se trate de gráficos sencillos, se puede utilizar la función Teorema de Erdos-Gallai que caracteriza cuándo una secuencia de grafos admite una representación gráfica.

Utilizando el teorema anterior se puede comprobar que se necesitan al menos tres vértices de grado $5$ lo que le da la secuencia de grados $ds = (7,7,7,7,7,7,7,5,5,5).$ Teniendo en cuenta esto se puede construir el siguiente gráfico realizando $ds.$

Answer 3

Como todos los grados son Impares, el número total de vértices debe ser par, por lo que el número de vértices de grado $5$ debe ser impar.

Con un solo vértice de grado $5$ la secuencia de grados es $(7,7,7,7,7,7,7,5)$ entonces el gráfico complementario tiene una secuencia de grados $(0,0,0,0,0,0,0,2)$ , lo cual es imposible.

Así que vamos a intentar un gráfico con la secuencia de grados $(7,7,7,7,7,7,7,5,5,5)$ . La secuencia de grados del gráfico complementario sería $(2,2,2,2,2,2,2,4,4,4)$ . Esto es muy fácil de realizar: empezar con un $10$ -ciclo, elegir tres vértices no adyacentes y unirlos entre sí con aristas.

Por lo tanto, el valor mínimo posible de $n$ es $10$ .