# 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?

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?

• When you assume that there is such long path? Feb 23, 2017 at 20:08
• Oh, sorry, I misread your comment :) Note that if the minimal degree is $0$ then we can proceed by induction, removing any degree-$0$ vertex. So I don't think we need to use connectedness at all. Feb 24, 2017 at 6:50
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.
Let $$G=(V,E)$$ be a connected graph, where $$|V|≤|E|$$. Assume that $$G$$ has no cycles. Since $$G$$ is connected and has no cycles, $$G$$ must be a tree. But in a tree, $$|E|=|V|-1.$$ i.e. $$|V|>|E|$$, which is a contradiction. Thus our assumption is false. Therefore, $$G$$ has a cycle.