Prove a simple connected graph with n nodes and at least n edges has a cycle.

Question

Proof that a graph with n nodes and m edges such that $ m \geq n \geq 3 $ has a circuit

After thinking about it for a while, I have few directions of how to approach the problem, yet I seem to be missing something.

I understand this is somewhat simple and intuitive problem, yet I can't come up with a proper proof.

Any kind of help will be most welcome.

Answer 1

Hint: Try strong induction by $n$.

When $n=3$, since $m \geq 3$, and your graph is a subgraph of $K_3$ it follows taht $G=K_3$.

$P(1),..,P(n) \Rightarrow P(n+1):$ Erase one edge.

Case 1): The graph stays connected, show that then the edge you erased must be part of a cycle.

Case 2): The graph disconects. Let $m_1,m_2$ be the number of edges in the two components and $n_1,n_2$ the number of vertices.

As $$m_1+m_2 \geq n_1+n_2-1$$ you must have $$m_1 \geq n_1$$ or $$m_2 \geq n_2$$

Use the inductive step.

Answer 2

Suppose we have smallest connected graph such that it does not contain a cycle and $V(G)\le E(G)$. Select a vertex $v$ arbitrary. If $d(v) = 1$, delete it, remaining graph still is connected but has smaller size and $V(G') \le E(G')$, contradiction. If $deg(v) > 1$ remove one of edges of $v$. Now we have at least two smaller graphs such that at least one of them has $E(G')\ge V(G')$ and still without cycle, again contradiction.