Graficando grafos en el plano

---

• (grafos planares)
• (def 1: arco)
• (def 2: dibujo de un grafo)
• (def 3: conjunto conexo)
• (dibujo sobre otras superficies)
• (superficie esférica)
• (superficie del toro)
• (superficie de la cinta del Mobius)
• (esfera con dos asas)
• (esfera con tres asas)
• (botella de Klein)(obs)
• (K_(3,3) y K_5 no son planares)
• (K_5 sobre el toro)
• (K_(3,3) sobre la banda de Mobius)
• (proposición 1)
• (def 4: género de un grafo planar)
• (ciclos en grafos planares)
• (def 5: curva de Jordan ; teorema 1: teorema de curva de Jordan)
• (proposición 2)
• (representación gráfica)(ejm 2)(caras y ciclos en grafos 2-conexos)
• (proposición 3 ; teorema 2)
• (fórmula de Euler)
• (teorema 1)
• (def 1: poliedro regular)
• (poliedros regulares)
• (proposición 1)
• (proposición 2)
• (proposición 3)
• (coloración de mapas)
• (def 2: coloración )(obs)
• (propiedades)(ejm)
• (def 3: grafo gradual)(ejm)
• (teorema 2 ; proposición 4)
• (números cromáticos conocidos)
• (polinomio cromático)
• (polinomios cromáticos de algunos grafos)(ejm: polinomio cromático del grafo lineal L_n)
• (asdasd)

---

• (sesión 13)
• PARTE I. TEORÍA FUNDAMENTAL
• Grafos planares
• Fórmula de Euler
• Consecuencias importantes de la fórmula de Euler
• PARTE II. EJERCICIOS RESUELTOS SOBRE LA FÓRMULA DE EULER
• 🟢 Ejercicio 4. Calcular vértices, aristas y caras
• 🟢 Ejercicio 5. Calcular aristas conociendo las caras
• 🟡 Ejercicio 6. Grafos planares con caras triangulares
• 🟡 Ejercicio 7. Grafos planares con caras cuadriláteras
• 🔴 Ejercicio 8. Demostrar la desigualdad E \leq 3V-6
• PARTE III. GRAFOS PLANARES MAXIMALES
• ¿Qué es un grafo planar maximal?
• 🟢 Ejercicio 9. Identificar un grafo planar maximal
• 🟡 Ejercicio 10. Número de aristas de un grafo planar maximal
• 🔴 Ejercicio 11. Demostrar que un grafo planar maximal tiene todas sus caras triangulares
• PARTE IV. GRAFOS HOMEOMORFOS
• 5. ¿Qué significa que dos grafos sean homeomorfos?
• ¿Qué es subdividir una arista?
• 🟢 Ejercicio 12. Identificar grafos homeomorfos
• 🟡 Ejercicio 13. Subdivisión y fórmula de Euler
• PARTE V. TEOREMA DE KURATOWSKI
• 6. Teorema de Kuratowski
• Los dos grafos fundamentales (Grafo completo \(K_5\) y Grafo bipartito completo \(K_{3,3})
• 🟢 Ejercicio 14. Demostrar que \(K_5\) no es planar
• 🟢 Ejercicio 15. Demostrar que \(K_{3,3}\) no es planar
• 🟡 Ejercicio 16. Grafo obtenido subdividiendo \(K_{3,3}\)
• 🔴 Ejercicio 17. Detectar una subdivisión de \(K_{3,3}\)
• PARTE VI. GÉNERO DE UN GRAFO
• 7. ¿Qué es el género de un grafo?
• 8. Fórmula de Euler para superficies orientables
• 🟢 Ejercicio 18. Calcular el género de una superficie
• 🟡 Ejercicio 19. Calcular caras en un toro
• 🟡 Ejercicio 20. Calcular el número de aristas sobre una superficie de género 2
• PARTE VII. PROBLEMAS COMBINADOS DE NIVEL EXAMEN
• 🔴 Ejercicio 21. Demostrar que todo grafo planar simple tiene un vértice de grado menor o igual que 5
• 🔴 Ejercicio 22. Determinar si un grafo regular puede ser planar
• 🔴 Ejercicio 23. Determinar si un grafo bipartito puede ser planar
• 🔴 Ejercicio 24. Grafo planar maximal y grados
• PARTE VIII. EJERCICIOS DE GÉNERO MÁS AVANZADOS
• 🔴 Ejercicio 25. Género del grafo completo \(K_n\)
• 🔴 Ejercicio 26. Género del grafo bipartito completo \(K_{m,n}\)
• PARTE IX. EJERCICIOS TEÓRICOS DE VERDADERO O FALSO
• Ejercicio 27. Determina si las siguientes afirmaciones son verdaderas o falsas
• PARTE X. EJERCICIOS ADICIONALES QUE CONVIENE DOMINAR
• 🔴 Ejercicio 28. ¿Puede existir un grafo planar con 8 vértices y 19 aristas?
• 🔴 Ejercicio 29. ¿Puede existir un grafo planar bipartito con 10 vértices y 17 aristas?
• 🔴 Ejercicio 30. Número de caras de un grafo planar maximal
• 🔴 Ejercicio 31. Un árbol y la fórmula de Euler
• 🔴 Ejercicio 32. Demostrar que un grafo planar simple bipartito cumple \(E\leq2V-4\)
• PARTE XI. CÓMO IDENTIFICAR QUÉ MÉTODO UTILIZAR EN UN EXAMEN
• PARTE XII. FORMULARIO COMPLETO PARA EL EXAMEN
• PARTE XIII. SIMULACRO DE EXAMEN
• CONCLUSIÓN: ¿QUÉ DEBES DOMINAR SÍ O SÍ?
• (sesión 14 - 6, 9, 14, 20, 22, 25, 27 y 29)
• 1. Resumen de teoría y fórmulas fundamentales
• 1.1. Grafo extraplanar
• 1.2. Teorema de Wagner
• 1.3. Coloración de vértices
• 1.4. Teorema de Brooks
• 2. Ejercicios resueltos: grafos extraplanares 
• Ejercicio 1. Determinar si un grafo es extraplanar
• Ejercicio 2. Demostrar que K_4 no es extraplanar
• Ejercicio 3. Número máximo de aristas
• Ejercicio 4. Caras de un grafo extraplanar maximal
• Ejercicio 5. Demostrar la cota m \leq 2n-3
• Ejercicio 6. Determinar si K_{2,3} es extraplanar
• 3. Ejercicios resueltos: teorema de Wagner
• Ejercicio 7. Aplicar Wagner a K_5
• Ejercicio 8. Demostrar que K_{3,3} no es planar
• Ejercicio 9. Encontrar un menor K_5 mediante contracciones
• Ejercicio 10. Distinguir menores y subgrafos
• Ejercicio 11. Demostrar que un grafo es planar usando Wagner
• 4. Ejercicios resueltos: coloración de vértices 
• Ejercicio 12. Número cromático de un grafo completo
• Ejercicio 13. Número cromático de ciclos
• Ejercicio 14. Colorear un grafo a partir de sus aristas
• Ejercicio 15. Número cromático de un grafo bipartito completo
• Ejercicio 16. Número cromático de un grafo rueda
• Ejercicio 17. Número cromático de la unión de grafos
• 5. Ejercicios resueltos: teorema de Brooks 
• Ejercicio 18. Aplicación directa del teorema de Brooks
• Ejercicio 19. Reconocer las excepciones de Brooks
• Ejercicio 20. Combinar clique y teorema de Brooks
• Ejercicio 21. ¿Es suficiente conocer el grado máximo?
• 6. Ejercicios de demostración 
• Ejercicio 22. Demostrar que todo grafo extraplanar es 3-coloreable
• Ejercicio 23. Demostrar que todo árbol es 2-coloreable
• Ejercicio 24. Demostrar que un grafo es bipartito si y solo si es 2-coloreable
• 7. Problemas integradores de nivel examen 
• Ejercicio 25. Extraplanaridad y número cromático
• Ejercicio 26. Planaridad, extraplanaridad y coloración
• Ejercicio 27. Grafo con grado máximo 3 y triángulo
• Ejercicio 28. Demostrar que un grafo no es planar utilizando un menor
• Ejercicio 29. Determinar el número cromático exacto usando cotas
• 8. Verdadero o falso: preguntas teóricas de examen
• 9. Ejercicios adicionales para practicar
• 10. Cómo identificar qué teorema utilizar en un examen
• 11. Fórmulas que debes memorizar sí o sí
• 12. ¿Qué ejercicios debes dominar para tu examen?
• (sesión 15)
• PARTE I. 
• PARTE II. EJERCICIOS RESUELTOS SOBRE POLINOMIOS CROMÁTICOS
• EJERCICIO 1. Polinomio cromático de un grafo sin aristas (Aplicación directa de la definición)
• EJERCICIO 2. Polinomio cromático de un camino (Cálculo mediante el principio multiplicativo).
• EJERCICIO 3. Polinomio cromático de un grafo completo (Aplicación de una fórmula fundamental).
• EJERCICIO 4. Polinomio cromático de un árbol (Reconocer la estructura del grafo).
• EJERCICIO 5. Polinomio cromático de un ciclo (Aplicación de la fórmula para ciclos).
• EJERCICIO 6. Determinar el número cromático a partir del polinomio (Interpretación de un polinomio cromático).
• PARTE III. FÓRMULA DE ELIMINACIÓN Y CONTRACCIÓN DE ARISTAS
• PARTE IV. EJERCICIOS RESUELTOS CON ELIMINACIÓN-CONTRACCIÓN
• EJERCICIO 7. Calcular el polinomio cromático de un triángulo mediante eliminación-contracción Tipo: Aplicación básica de la fórmula.
• EJERCICIO 8. Calcular el polinomio cromático de un cuadrado mediante eliminación-contracción Tipo: Aplicación a un ciclo.
• EJERCICIO 9. Polinomio cromático de un cuadrado con una diagonal Tipo: Grafo compuesto con ciclos.
• EJERCICIO 10. Polinomio cromático de un grafo formado por dos triángulos que comparten un vértice Tipo: Descomposición de grafos.
• EJERCICIO 11. Polinomio cromático de dos componentes desconectadas Tipo: Propiedad multiplicativa.
• PARTE V. EJERCICIOS DE MAYOR DIFICULTAD
• EJERCICIO 12. Polinomio cromático de un ciclo de cinco vértices Tipo: Aplicación de una fórmula y factorización.
• EJERCICIO 13. Polinomio cromático de un grafo con un vértice universal Tipo: Reconocimiento de estructuras especiales.
• EJERCICIO 14. Demostrar la fórmula del polinomio cromático de un árbol Tipo: Demostración matemática.
• EJERCICIO 15. Demostrar la fórmula del polinomio cromático de un ciclo mediante eliminación-contracción Tipo: Demostración utilizando una recurrencia.
• PARTE VI. PROPIEDADES IMPORTANTES DEL POLINOMIO CROMÁTICO
• EJERCICIO 16. Identificar información de un grafo a partir de su polinomio Tipo: Interpretación de coeficientes.
• EJERCICIO 17. ¿Pueden dos grafos diferentes tener el mismo polinomio cromático? Tipo: Pregunta conceptual con contraejemplo.
• PARTE VII. PROBLEMAS ADICIONALES DE EXAMEN
• EJERCICIO 18. Aplicar eliminación-contracción a un grafo con una arista puente Tipo: Uso de la fórmula en grafos con puentes.
• EJERCICIO 19. Calcular el polinomio cromático de un grafo completo bipartito K_{2,3} Tipo: Conteo por casos.
• PARTE VIII. PREGUNTAS TEÓRICAS DE VERDADERO O FALSO
• PARTE IX. EJERCICIO INTEGRADOR TIPO EXAMEN
• EJERCICIO 20. Cálculo, eliminación-contracción y número cromático
• PARTE X. PROPIEDADES ADICIONALES QUE CONVIENE CONOCER
• PARTE XI. ¿CÓMO RECONOCER QUÉ MÉTODO UTILIZAR EN UN EXAMEN?
• PARTE XII. ERRORES FRECUENTES EN LOS EXÁMENES
• PARTE XIII. RESUMEN DE FÓRMULAS PARA MEMORIZAR
• PARTE XIV. ¿QUÉ EJERCICIOS DEBES DOMINAR SÍ O SÍ?
• (sesión 16)
• (sesión 17)
• (sesión 18)

---

(grafos planares)(def 1: arco)(def 2: dibujo de un grafo)(def 3: conjunto conexo)(dibujo sobre otras superficies)(superficie esférica)(superficie del toro)(superficie de la cinta del Mobius)(esfera con dos asas)(esfera con tres asas)(botella de Klein)(obs)(K_(3,3) y K_5 no son planares)(K_5 sobre el toro)(K_(3,3) sobre la banda de Mobius)(proposición 1)(def 4: género de un grafo planar)(ciclos en grafos planares)(def 5: curva de Jordan ; teorema 1: teorema de curva de Jordan)(proposición 2)(representación gráfica)(ejm 2)(caras y ciclos en grafos 2-conexos)(proposición 3 ; teorema 2)

(fórmula de Euler)(teorema 1)(def 1: poliedro regular)(poliedros regulares)(proposición 1)(proposición 2)(proposición 3)(coloración de mapas)(def 2: coloración )(obs)(propiedades)(ejm)(def 3: grafo gradual)(ejm)(teorema 2 ; proposición 4)(números cromáticos conocidos)(polinomio cromático)(polinomios cromáticos de algunos grafos)(ejm: polinomio cromático del grafo lineal L_n)

---