[carambola]

Demostrar la siguiente proposición:

Sea \( G = (V, E) \) un grafo conexo y $$E',\widehat{E}\subset E$$ tal que el grafo \( (V, E) \) no tiene ciclos y $$|E'|<|\widehat{E}|$$. Probar que existe $$e\in \widehat{E}$$ que conecta vértices de diferentes componentes conexas del grafo \( (V, E') \).


Gracias!!

[Luis Fuentes]

Hola

Sea \( G = (V, E) \) un grafo conexo y $$E',\widehat{E}\subset E$$ tal que el grafo \( (V, E) \) no tiene ciclos y $$|E'|<|\widehat{E}|$$. Probar que existe $$e\in \widehat{E}$$ que conecta vértices de diferentes componentes conexas del grafo \( (V, E') \).

Si \( G \) es conexo y sin ciclos es un árbol. Entonces cada componente conexa de \( (V,E') \) es un árbol. Si \( |E'|=a \), entonces la componente conexa más grande a lo sumo tiene \( a+1 \) vértices y \( a \) aristas. Si \( |\widehat{E}|=b>a \) entonces las aristas de \( E' \) no puden en estar en una sola componente conexa  de \( (V,E') \), ya que hemos visto que a lo sumo tienen \( a \) aristas.

Saludos.