# If a graph with $n$ vertices and $n$ edges there must a cycle?

How to prove this question? If a graph with $n$ vertices and $n$ edges it must contain a cycle?

• Am I right to assume that you mean a cycle? Jun 8 '13 at 14:16
• I'm guessing he means "contains a cycle". I misread it first.
– mrf
Jun 8 '13 at 14:21
• Sometimes circle is used to mean cycle (as noted on Wikipedia (ref.)), but I think this is rare. Jun 14 '13 at 13:29

Assume that $G$ contains no cycles. Then every connected component of $G$ is a tree.

Claim The number of edges in a tree on $n$ vertices is $n-1$.

Proof is by induction. The claim is obvious for $n=1$. Assume that it holds for trees on $n$ vertices. Take a tree on $n+1$ vertices. It's an easy exercise (look at a longest path in $G$) to show that a tree has at least one terminal vertex (i.e. with degree $1$). Removing this terminal vertex along with its edge, we get a tree on $n$ vertices, and induction takes us home.

Hence the number of edges in a graph without cycles is $n-k$, where $k$ is the number of connected components.

Here's is an approach which does not use induction:

Let $G$ be a graph with $n$ vertices and $n$ edges. Keep removing vertices of degree $1$ from $G$ until no such removal is possible, and let $G'$ denote the resulting graph. Note that in each removal, we're removing exactly $1$ vertex and $1$ edge, so $G'$ cannot be empty, otherwise before the last removal we'd have a graph with $1$ vertex and $1$ edge, and $G'$ has the same number of vertices and edges. Therefore the minimum degree in $G'$ is at least $2$, which implies that $G'$ has a cycle.

• How is that "not using induction"?
– mrf
Mar 21 '19 at 15:32

Here's another approach:

Let $$P = a_1, a_2, \dots, a_n$$ be a simple path of maximal length in G.

Since the degree of each vertex is greater than two, there exists a vertex $$b$$ such that $${b,a_1}$$ is an edge.

Now, there can be two cases:

1. $$b$$ is on the path P: In this case, the sub-path from $$a_1$$ to $$b$$ and the edge from $$b$$ to $$a_1$$ forms a cycle.

2. $$b$$ is not on the path P: In this case, the path $$b,a_1,a_2, \dots, a_n$$ is a path of greater length than $$P$$, thus contradicting our assumption.

Source