Prove that every $n$-vertex graph with at least $n$ edges contains a cycle

Question

I am hoping someone could review my proof of the following claim. Thanks in advance!

Claim: Every $n$-vertex graph with at least $n$-edges contains a cycle.

Proof:

Let $G$ be a $n$-vertex graph with at least $n$-edges.
Suppose $G$ contains no cycle. Then $G$ contains no closed trails, as in any $v-v$ trail there is a $v-v$ cycle.

Then consider the following procedure:

• Step 1: Pick an edge $e_i \in E(G)$ and construct a maximal trail from $e_i$.
  This trail must be a path, as any repeated vertex would create a cycle. This path yields $x$ vertices and $x-1$ edges.

• Step 2:
  Pick any edge not previously included in any path, call this edge $e_j$.
  Construct a maximal path from $e_j$.

This path is either incident to some vertex we have previously used on a previous path or not.

• If not, then the path from $e_j$, call it $P_j$, has $y$ vertices and $y-1$ edges.
• If so, then when $P_j$ hits a vertex, $v$, on a previous maximal path, it must follow along with that path to its end or reverse course along that path to its beginning (the initial edge that began that path). If it goes to its end, then $P_j$ adds $y$ vertices, $y$ edges up to $v$, as we cannot double count $v$, then no new edges and vertices after that.

If $P_j$ reverses course along this previously seen path, it added $y$ edges and $y$ vertices up to $v$, then at most adds $w$ vertices and $w$ edges after it potentially passes the starting point of the previously counted path.

We continually repeat step $2$ until edges belong to some maximal path we construct. But at each point in the process, we add at most the same number of vertices and edges and there is guaranteed at step one at least some path of length $x$ vertices and $x-1$ edges. But this contradicts G having at least as many edges as it has vertices, that is $n$ vertices and $\ge n$ edges.

Hence $G$ must have a cycle.

Answer 1

I think it's correct but too complicated. Here is (a sketch of) a somewhat easier proof. We assume that graphs are finite.

First, if a graph has at least as many edges as vertices, then it has a subgraph in which every vertex has degree at least $2$. For, if some vertex has degree less than $2$, then we can delete that vertex and its incident edge (if any), and the resulting subgraph still has at least as many edges as vertices. Repeat as needed.

Now suppose every vertex has degree at least $2$. Pick any vertex as a starting point and start walking on the edges, without traversing any edge twice. Every time you arrive at a new vertex you will be able to leave it, since the degree is at least $2$. Since the number of vertices is finite, eventually you must revisit a vertex, and then the portion of your walk between your two visits to that vertex will be a cycle.

Answer 2

The general thrust of your argument is fine. You're missing a lot of details that make it difficult to follow exactly what you're proposing to do, so that would require a lot of attention.

Personally, I think you got a lot more bogged down in the process of constructing your example than you need to be to make an effective argument, and those details are clouding your central point. For instance, without those details you could simply say:

Choose $T$ to be some acyclic subgraph of $G$ with the maximal number of edges (i.e. a spanning forest). We know from previous exercises that the number of edges in $T$ is $n-\omega$, where $\omega$ is the number of components of $G$. Since $G$ has $n$ edges, we may choose $e\in G-T$. $T+e$ cannot be acyclic, because $T$ was given to be maximal. Therefore, that subgraph of $G$ contains a cycle. Clearly then, $G$ contains a cycle as well.

See how the argument becomes much simpler to write and follow when you don't bother to show where the cycle is?

Answer 3

I think your proof is correct. I show you an alternative proof by contradiction which still uses the idea of picking a path of maximal length.

Suppose that the claim is not true for all positive integers; let $n$ be the smallest positive integer for which the claim does not hold.
Hence, there exists a cycle-free graph $G$ with $n$ vertices and $n$ edges. Let $P=x_0x_1...x_k$ be a path of maximal length in $G$. Suppose that $x_0$ has degree $\geq2$, then there exists a vertex $v\not=x_1$ which is a neighbor of $x_0$.

If $v$ is a vertex in $P$, say $v=x_j$, then $vx_0x_1...x_jv$ is a cycle, contradiction.
If $v$ is not a vertex in $P$, then $vx_0x_1x_k$ is a path which is longer than $P$, again contradiction.
This implies that $v$ must have degree 1.

Consider the graph $G'=G-x_0$, ie the graph obtained by deleting the vertex $x_0$ and the edge $x_0x_1$ from $G$. $G'$ is a cycle-free grap which has $n-1$ vertex and $n-1$ edges. Thus the claim does not hold for $n-1$; but by assumption $n$ was the smallest positive integer for which the claim does not hold, so we have a contradiction.