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.
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.
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.