Para la parte a) propongo la demostración adjunta y quisiera saber si les parece correcta.
Saludos y gracias.
La demostración es incorrecta, pues 
no es el peor caso sino el mejor, pues te da muchos colores para pintar. El tema es cuando 
es pequeño, por ejemplo para el grafo de Petersen es 3, y ¿porque podés pintarlo con 4 colores?
Saludos