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

Question

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.

Answer 1

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.

Answer 2

There are a couple of problems with your argument. First, as Banach Tarski pointed out, $G$ doesn’t contain a spanning tree unless it’s connected. Secondly, the non-existence of vertices of degree $1$ in $G$ does not imply that every vertex of $G$ has degree at least $2$: $G$ may have isolated vertices, vertices of degree $0$. Finally, your induction hypothesis is that each graph on fewer than $n$ vertices with as many edges as vertices contains a cycle; it does not say that a graph with $n-1$ edges has a cycle unless that graph has $n-1$ vertices, which yours does not. Thus, your attempt to apply your induction hypothesis is invalid. An induction argument is nonetheless possible; I suggest one possibility below.

HINT: Suppose first that $G$ is not connected, and let the components of $G$ be $G_1,\ldots,G_m$. For $k=1,\ldots,m$ let $n_k$ be the number of vertices of $G_k$ and $e_k$ the number of edges.

• Explain why $e_k\ge n_k-1$ for $k=1,\ldots,m$.
• Show that there must be a $k\in\{1,\ldots,m\}$ such that $e_k\ge n_k$, and explain why that $G_k$ must contain a cycle.

Now suppose that $G$ is connected. Then $G$ has a spanning tree $T$. Let $e=uv$ be the edge of $G$ that is not in $T$, and explain how to construct a cycle in $G$ that contains the edge $e$.