If there are more edges than vertices in a connected graph then there is a cycle in the graph I have a simple question and probably stupid in graph theory:

Prove that if there are more edges than vertices in a connected graph then there is a cycle:
Let $G=(V,E)$ a connected graph,where $|V| \le |E|$.Prove that there is a cycle in the graph.

How can I prove that?
 A: Consider a vertex of minimal degree. If the degree was $1$, then we're done by induction if we remove that vertex. Otherwise, the minimal degree in the graph is at least $2$. Take a longest path $v_0 v_1 \dots v_k$; then $v_0$ has degree $2$ or higher, so the only way this can be a longest path is if $v_0$ is connected to some other $v_i$ than $v_1$. (If not, if $v_0$ is connected to $x$ which is not a $v_i$, then we could extend the path by adding $x$.) So we have found a cycle.

Why is there a longest path? There is certainly a path of length $1$ (pick any vertex!). There are only finitely many paths, since there are only $|V|$ vertices. So we can just list the paths, and their lengths; at least one of them will have longest length (because every finite set has a maximum).

Question for you: where have we used that the graph was connected?
A: Let $n := \vert V \vert$.
Since $G$ is connected, there is a walk $\gamma$ passing through all $n$ points of $G$ and having at least length $(n-1)$.
If $\gamma$ has length $> (n -1)$ there is a vertex that $\gamma$ passes through twice, implying that it contains a cycle.
If its length is exactly $(n-1)$ there is some edge $e \in E$ which is unused in $\gamma$ (since $\vert E \vert \geq n$) and by combining it with $\gamma$ we get a cycle.

You can now use this to show that any graph with $\vert V\vert \leq \vert E \vert $ contains a cycle.
Let $G_k = (V_k, E_k)$ denote the connected components of $G$ and assume that $\forall k: \, \vert V_k \vert > \vert E_k \vert $. Then we have
$$
  \vert V \vert = \sum_k \vert V_k \vert > \sum_k \vert E_k \vert = \vert E \vert
$$
which contradicts $\vert V\vert \leq \vert E \vert $. So there must be a connected component $G_k$ with $\vert V_k \vert \leq \vert E_k \vert $, which then contains a cycle by the first part.
