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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.