Buenas,
La parte 1. es el teorema 12.3 del Grimaldi. Podés encontrar la demostración en la página 609.
Para la parte 2. podés usar la parte 1. para demostrarlo. Si
fuera conexo y le agregamos una arista cualquiera, entonces el grafo resultante (llamemosle 
) tiene que seguir siendo conexo y además cumple que tiene 
aristas. Por la parte 1. este grafo tiene que ser un arbol. Ahora como es un arbol, existe un único camino que conecta dos vértices distintos, si le quitamos una arista a el grafo resultante no puede ser conexo. Y por lo tanto tampoco puede ser conexo.
Saludos,
Agustín
La parte 1. es el teorema 12.3 del Grimaldi. Podés encontrar la demostración en la página 609.
Para la parte 2. podés usar la parte 1. para demostrarlo. Si
fuera conexo y le agregamos una arista cualquiera, entonces el grafo resultante (llamemosle ) tiene que seguir siendo conexo y además cumple que tiene aristas. Por la parte 1. este grafo tiene que ser un arbol. Ahora como es un arbol, existe un único camino que conecta dos vértices distintos, si le quitamos una arista a el grafo resultante no puede ser conexo. Y por lo tanto tampoco puede ser conexo.Saludos,
Agustín