[Math] A graph with an equal number of edges and vertices contains a cycle as a subgraph

combinatoricsgraph theory

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:

Try to use the inductive hypothesis on each connected component of the graph.

Hint 2:

Use the fact that a connected component with $r$ number of nodes must have $\ge r-1$ edges.

Hint 3:

Use the fact that the sum of the edges of all connected components must be equal to $n$, the number of nodes in the graph.

Hint 4:

If there are $r \ge 1$ connected components, then the total number of edges in these connected components is $ m \ge n - r$. But we know that $m = n$ which implies that at least one connected component with $l$ number of nodes has more than $l-1$ edges. Now use the inductive hypothesis.

Related Question