Si un grafo $G=\left<V,E\right>$ está conectado y $\left|E\right|=\left|V\right|$ entonces hay un ciclo en $G$

Question

Probar: Si un grafo, $G =\left$ es conexo y $|E|=|V|$ entonces hay un ciclo en $G$

Creo que esto debería ser demostrado por inducción. Esto ciertamente se cumple para $n=1$ (un vértice con bucle).

Ahora, para el caso general, supongo que cada vértice en el grafo debe tener grado $2$, lo cual debería ayudar a completar la prueba. Pero ¿cómo exactamente?

Lo que he hecho hasta ahora:

La igualdad $$\sum\limits_{v\in V} d(v) = 2\left|E\right|$$ es verdadera para cualquier grafo, y $|E|=|V|$ a partir de la suposición de la pregunta, por lo tanto $$\sum\limits_{v\in V} d(v) = 2\left|V\right|$$

Answer 1

Sea $|E|=|V|=n+1$, y supongamos que el resultado está probado para grafos de tamaño $n$.

Si $G$ no tiene ciclos, es un árbol (por definición). En un árbol, hay vértices de grado $1$ (las hojas), así que sea $v$ una hoja, y sea $e$ la única arista adyacente a $v$. Entonces el grafo $(V\setminus\{v\}, E\setminus\{e\})$ tiene $n$ vértices y tantas aristas como vértices, y es conexo, así que por hipótesis de inducción, tiene un ciclo $e_1\cdots e_k$. ¿Ves cómo terminar?