Ricardo A. Sáenz

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 Muestra que 6 puntos genéricos en el plano forman al menos 3 cuadriláteros convexos. Encuentra 8 puntos genéricos en el plano que no contienen un pentágono convexo. Problema 5 ¿Es planar el grafo que resulta de eliminar una arista de $latex K_5$? ¿Es planar el complemento de un ciclo de longitud 6? ¿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 2 n -4 aristas. Problema 8 Muestra que

Fecha de entrega: 22 de abril Problema 1 Muestra que un árbol es un grafo bipartito. ¿Es cierto que todo grafo bipartito es un árbol? Problema 2 ¿Existe un grafo bipartito con vértices de grados 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 6 y 6? Un grafo bipartito tiene 16 vértices de grado 5 y cierto número de vértices de grado 8. Si sabemos que los vértices de grado 8 se encuentran en el mismo lado, ¿cuántos vértices de grado 8 puede tener? Problema 3 Sea  G un grafo bipartito con el mismo número de nodos de cada lado tal que cada  k vértices del lado izquierdo tienen  k +1 vecinos del lado derecho. Muestra que cada arista de  G se puede extender a un apareamiento perfecto. Problema 4 Muestra que un grafo bipartito en el cual todos sus vértices tienen el mismo grado tiene un apareamiento perfecto. Da un ejemplo de un grafo con todos sus vértices del mismo grado que no tiene un apareamiento perfecto. Problema 5 Muestra que, si  G tiene un apareamiento perfecto, entonces todo apaream

Fecha de entrega: 15 de abril Problema 1 Encuentra el número de árboles no etiquetados con 6 vértices. Una  estrella doble es un árbol con exactamente dos vértices con grado mayor que 1. ¿Cuántas estrellas dobles hay con  n vértices? Problema 2 Considera una matriz de $latex 2\times n-1$, cuyo primer renglón está formado por los números del 1 al $latex n-1$, y el segundo por números arbitrarios entre 0 y $latex n-1$. Construye el grafo con vértices $latex 0,1,2\ldots,n-1$ y aristas descritas por las columnas de esta matriz. Muestra que este grafo no siempre es un árbol. Demuestra que, si este grafo es conexo, entonces es un árbol. Muestra que cada componente conexa tiene a lo más un ciclo. Problema 3 Construye los árboles descritos por las siguientes codificaciones de Prüfer . 433 10520 44444 16976762 426641 Problema 4 Construye los árboles descritos por las siguientes codificaciones planares 11110000 11100100 11010100 11010010 11001010 Pr

Fecha de entrega: 8 de abril Problema 1 Demuestra que al conectar dos vértices  u y  v en un grafo G  con una nueva arista, se crea un nuevo ciclo si y solo si  u y  v se encuentran en la misma componente conexa de  G . Problema 2 Muestra que, en un árbol, cualquiera dos vértices pueden ser conectados por una única trayectoria. De manera inversa, muestra que si en un grafo cualquiera dos vértices pueden ser conectados por una única trayectoria, entonces el grafo es un árbol. Problema 3 Completa la demostración del teorema visto en clase:  Todo árbol con al menos dos vértices tiene al menos dos vértices de grado 1. Problema 4 Sea  G un grafo conexo y  e una arista de  G . Muestra que  e no es una arista de corte si y solo si e es parte de un ciclo en  G . Problema 5 Muestra que un árbol con un vértice de grado  d  tiene al menos  d hojas.