Tarea 13, Matemáticas discretas

Fecha de entrega: 18 de mayo

Problema 1

1. ¿Es planar el grafo que resulta de eliminar una arista de $latex K_5$?


2. ¿Es planar el complemento de un ciclo de longitud 6?


3. ¿Es planar el grafo que resulta de agregar a un hexágono sus tres diagonales principales?

Problema 2

Supón que queremos unir tres casas a tres pozos. ¿Es posible hacerlo sin que los caminos se crucen?

Problema 3

Muestra que un grafo planar bipartito, con n vértices, puede tener a lo más 2n-4 aristas.

Problema 4

Muestra que un polihedro convexo, que solo tiene caras pentagonales y hexagonales, debe tener exactamente 12 caras pentagonales.

Problema 5

Muestra que los siguientes grafos no son 3-coloreables.

Problema 6

Considera n rectas genéricas en el plano, y considera el grafo formado por sus puntos de intersección y los segmentos de recta entre ellos. Muestra que este grafo es 3-coloreable.

Problema 7

Muestra el corolario visto en clase: si G es un grafo tal que cada subgrafo de G tiene al menos un vértice de grado d, entonces G es (d+1)-coloreable.