Demostrar que no hay ningún gráfico bipartito en $14$ vértices con esta secuencia de grado.

Question

<blockquote> <p>Demostrar que no hay ningún gráfico bipartito en $14$ vértices con grado secuencia: $$6, 6, 6, 6, 6, 6, 6, 6, 5, 3, 3, 3, 3, 3.$ $</p> </blockquote> <p>Supongo que un vértice con grado $5$ rompe este gráfico de ser bipartita.</p> <p>Estaba pensando dejar el número de vértices con grado de $3 = x$ y aquellos con grado de $5 = y$. Todavía estoy pensando qué hacer de allí...</p>

Answer 1

Porque la gráfica es bipartita, la suma de los grados de los vértices del lado izquierdo es igual a la suma de los grados de los vértices del lado derecho. Ambos son iguales a la mitad de la suma de los números que le dan. Usted necesita demostrar que ningún subconjunto de los números tiene una suma que es igual a la mitad de la suma de todos los números. Sugerencia: modular aritmética.

Answer 2

Si he contado correctamente, la suma de grado total es 68. Eso significa que cada lado de la bipartición debe tener una grado de suma de 34. Y 34 no es un múltiplo de 3 (así ningún lado puede tener una cantidad de grados que es un múltiplo de 3).

Ahora, tomar el lado de la bipartición que no tiene el vértice de grado 5. ¿Su suma de grado?