Tarea 11, Matemáticas discretas

Fecha de entrega: 29 de abril

Problema 1

Dadas al menos 3 rectas genéricas en el plano, muestra que entre las regiones en que dividen al plano se encuentra al menos un triángulo.

Problema 2

¿En cuántas regiones dividen al plano dos n-ágonos convexos?

Problema 3

¿Cuál es el mínimo y el máximo número de regiones en que dividen al plano n círculos?

Problema 4

1. Muestra que 6 puntos genéricos en el plano forman al menos 3 cuadriláteros convexos.


2. Encuentra 8 puntos genéricos en el plano que no contienen un pentágono convexo.

Problema 5

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 6

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

Problema 7

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

Problema 8

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