Tarea 8, Matemáticas discretas

Fecha de entrega: 13 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

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 3

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 4

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

Problema 5

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 6

Muestra que un árbol con un vértice de grado d tiene al menos d hojas.