Tarea 8, Matemáticas discretas

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.