Prove by induction that every graph with n vertices and at least n edges has a cycle

Prove by induction that every graph with $n$ vertices and at least n edges has a cycle. Use induction by $n$ and the fact that a graph in which every vertex has a degree $\ge 2$ has a cycle.

I'm thinking about removing vertices of degree 1 from the graph (so that I'm removing exactly one vertex and one edge) until I'm left with a graph in which every vertex has a degree at least 2, but I'm not sure how I should incorporate induction in this reasoning.

• The key when inducting is to replace words like "until" with "to get the $n-1$ case" which is already true. Show that removing a degree 1 vertex (if there aren't any we are already done) gives us a graph with $n-1$ vertices and edges, and we assume that a cycle exists in this graph.
– user211599
Apr 26 '18 at 20:22

Take two vertices that are connected by one edge. Call them $(u,v)$ and the edge $e$. Collapse the vertices into one vertex. You obtain a graph $G'$ on one less vertex and one less edge. Apply the induction hypothesis, and convince yourself that if you have a cycle in $G'$ then the uncollapsed version must also have a cycle.

• Short and sweet. Very nice! However, you do have to take care when it comes to common neighbors $u$ and $v$ may have
– Mike
Apr 26 '18 at 21:51
• If $u$ and $v$ have a common neighbor $w$, then that is a cycle too $(u,v,w)$
– Mike
Apr 26 '18 at 22:14

Assume that every graph with $n$ vertices and $m\geq n$ edges has a cycle.

We need to show that every graph with $n+1$ vertices and $m+1\geq n+1$ edges has a cycle. Let $G$ be a graph with $n+1$ vertices and $m+1$ edges, where $m+1\geq n+1$. If every vertex of $G$ has degree at least two, then you're done. Suppose $G$ has a vertex $v$ of degree $<2$.

If $\deg(v) = 0$, then one can remove the vertex $v$ and since no edges are connected to it, the resulting graph will have $n$ vertices and $m+1\geq n+1 > n$ vertices. By our assumption, this graph contains a cycle, which is also present in $G$.

If $\deg(v) = 1$, remove the vertex $v$ and the single edge that contains it from $G$. The resulting graph will have $n$ vertices and $m\geq n$ vertices. By our assumption, this graph contains a cycle, which is also present in $G$.

Regardless of the situation, $G$ contains a cycle, so our induction step is complete.

• I upvoted, but if I were an instructor grading this answer on a student's homework, I probably would be commenting "why does a graph where every vertex has degree at least 2 have a cycle?"
– Mike
Apr 26 '18 at 21:28
• @Mike Fair enough, but this is being assumed by the question (here on the site). So maybe this would have been proved in an earlier question, or in the text itself. Apr 27 '18 at 1:16

We make the necessary assumption that $G$ is simple. We also use the following:

Fact 1: The number of edges in $G$ is $\frac{1}{2}\sum_{v \in V(G)} d_v$, where $d_v$ is the degree of $v$ in $G$.

Let $G$ be a graph with $n$ vertices and $m \ge n$ edges. Then $d$ be the minimum-degree of a vertex in the graph. Remove a minimum-degree vertex $v$ from $G$. Then every remaining vertex has degree at least $d-1$. If $d$ is at least 3 then every vertex in $G \setminus \{v\}$ has degree at least $d-1 =2$, so by Fact 1 $G \setminus \{v\}$ has at least $n-1$ edges, so by induction $G \setminus \{v\}$ has a cycle.

If $d$ is 2 then we consider 2 cases. If $G \setminus \{v\}$ is connected, then let $a$ and $b$ be $v$'s neighbors in $G$ and let $P_{ab}$ be the path from $a$ to $b$ in $G \setminus \{v\}$. Then $P_{ab} + \{b,v\}+\{v,a\}$ is a cycle. If $G \setminus \{v\}$ is not connected, then there is a connected component $M$ of $G \setminus \{v\}$ that has as many edges as vertices. Indeed, otherwise $G \setminus \{v\}$, as it has $a \geq 2$ connected components and $n-1$ vertices, would have no more than $n-a-1$ edges, impossible since $G$ had $n$ edges and at least $n$ edges. Then $M$ has a cycle by induction.

If $d =1$ then removing a degree-1 vertex from $G$ decreases the number of edges and the number of vertices both by 1, so $G \setminus \{v\}$ still has at least as many edges as vertices and so by induction it has a cycle.

This clearly covers all possible cases.

Here is a proof by (strong) induction which does not use the fact that a graph with minimum degree at least $2$ has a cycle.

Let $T(n)$ denote the statement: every graph with $n$ vertices and at least $n$ edges has a cycle. Assuming that $T(m)$ holds for all $m\lt n,$ we prove that $T(n)$ holds.

Let $G$ be a graph with $n$ vertices and at least $n$ edges. Choose a vertex $v$ of $G.$ Let $G_1,\dots,G_k$ be the connected components of $G-v,$ and let $G_i$ have $n_i$ vertices and $e_i$ edges.

Case 1. For some $i$ we have $e_i\ge n_i.$

Then $G_i$ has a cycle by the inductive hypothesis $T(n_i).$

Case 2. For some $i$ there are at least two edges from $v$ to $G_i.$

So there are two edges joining $v$ to vertices $x,y$ in $G_i.$ Since $G_i$ is connected there is a path connecting $x$ to $y$ in $G_i,$ which together with the two given edges makes a cycle.

Case 3. For each $i$ we have $e_i\le n_i-1,$ and there is at most one edge from $v$ to $G_i.$ Then the degree of $v$ is at most $k,$ and the total number of edges in $G$ is at most $$(n_1-1)+\cdots+(n_k-1)+k=n_1+\cdots+n_k=n-1,$$ contradicting our assumption that $G$ has at least $n$ edges.