I'm trying to prove
A graph with an equal number of edges and vertices contains a cycle as
a subgraph
My attempt
Induction on the number of vertices:
Clearly holds for $n=3$
Assume true for all graphs on $\le n-1$ vertices.
For n:
Case 1: There is a vertex of degree 1, say $v$. Then $G = v \cup H$.
By hypothesis, H contains a cycle, so G necessarily contains a cycle.Case 2: No vertex of degree 1. So every vertex has degree $\ge 2$.
Take minimum spanning tree of G, which contains no cycles and has at
most $n-1$ edges. But our hypothesis says that any graph on $\le n-1$
edges contains a cycle. Contradiction.
I'm not sure about my case 2, any verification would be helpful.
Best Answer
Your proof is incorrect. A spanning tree exists if and only if the graph is connected. $deg(u) \ge 2 \not\implies G$ is connected. You haven't proved that the graph is connected.
Example: Consider this graph with 6 nodes and 6 edges: $1-2 , 2-3 , 3-1 , 4-5 , 5-6 , 6-1$
Hint 1:
Hint 2:
Hint 3:
Hint 4: