5
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

8
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ When you assume that there is such long path? $\endgroup$
    – ChikChak
    Feb 23, 2017 at 20:08
  • $\begingroup$ @TakaTiki Added to the answer. $\endgroup$ Feb 23, 2017 at 22:16
  • $\begingroup$ I meant,that we have used the fact that the graph was connected when you assumed that there is such a long path? $\endgroup$
    – ChikChak
    Feb 23, 2017 at 22:36
  • $\begingroup$ 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. $\endgroup$ Feb 24, 2017 at 6:50
  • 1
    $\begingroup$ @PedroAlves Remove that vertex; then find a cycle inductively (not a longest path, though the inductive "find a cycle" process may involve finding a longest path in the reduced graph). $\endgroup$ Nov 28, 2017 at 18:36
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .