Los deberes para estos días son los siguientes:

1. Repasar lo que consideréis necesario de inducción, recursividad y combinatoria.
2. Estudiar la sección 5.1.
3. Repasar desde 5.2.8 hasta 5.2.12. Respecto a la prueba del problema 5.2.8, alguien me preguntó si se podría probar sin contradicción. Creo que no, pero abajo tenéis otra prueba más simple que la que he dado en clase.
4. Hacer el ejercicio 5.2.13.
5. Estudiar desde 5.2.16 hasta 5.2.33

 

Problema 5.2.8:

Supongamos que tenemos un grafo simple G = (V,A) con n vértices y q aristas. Probaremos que la proposición es cierta por reducción al absurdo. La conclusión dice que hay al menos dos vértices con el mismo grado. La negación de esto sería que no hay dos vértices con el mismo grado.  La sucesión de grados va desde 0 hasta n-1. La sucesión que tiene los grados distintos es {0,1,2,…,n- 1}. Esta sucesión no se puede dar en ningún grafo porque grado 0 significa que el vértice es aislado y por otro lado grado n- 1 que otro vértice se une a todos. Supondría una contradicción.  Pero si el cero no puede estar, entonces ese vértice tendrá que tomar un valor entre 1 y n - 1, y ya están todos tomados. Luego habría una contradicción. Y esto prueba el teorema.