Tarea 7, Matemáticas discretas

Fecha de entrega: 18 de marzo

Problema 1

Formula y demuestra el siguiente enunciado como un teorema de grafos: "En un grupo de personas existen dos de ellas que conocen al mismo número de personas cada uno".

Problema 2

1. Por medio de un ejemplo, muestra que si eliminamos una arista de un grafo conexo G, el resultado puede ser un grafo disconexo.


2. Muestra que, si la arista eliminada pertenece a un ciclo subgrafo de G, entonces el resultado es conexo.

Problema 3

Sea G un grafo y u, v dos vértices de G.

1. Muestra que, si existe una caminata de u a v, entonces existe una trayectoria de u a v.


2. Utiliza el inciso anterior para dar una demostración distinta a la vista en clase para el siguiente enunciado: si p, q, y r son vértices de G tales que existe una trayectoria de p a q y una trayectoria de q a r, entonces existe una trayectoria de p a r.

Problema 4

Muestra que si el grafo G con n vértices tiene más de $latex \binom{n-1}{2}$ aristas, entonces es conexo.

Problema 5

Muestra que al menos uno de los grafos $latex G$ o $latex \overline G$ es conexo.

Problema 6

Determina cuáles de los siguientes 4 grafos tienen una caminata euleriana, y cuáles una caminata euleriana cerrada. Dibújala, si es el caso.

Problema 7

Determina cuáles de los siguientes 2 grafos tienen un ciclo hamiltoniano.