¿Existe un grafo bipartito con los siguientes grados: 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 6, 6? He probado muchas combinaciones diferentes y creo que no hay forma de hacer un grafo bipartito de esta manera, pero ¿alguien sabe cómo puedo probarlo?
Respuesta
¿Demasiados anuncios?
Primera pista: En un grafo bipartito, la suma de los grados de un lado es igual a la suma de los grados del otro lado (siendo cada suma igual al número de aristas). ¿Puedes dividir esos números en dos grupos con sumas iguales?
Segunda pista: Sólo uno de los números no es divisible por $3$ . Es decir, modulo $3$ , tienes once $0$ s y un $2$ .
