Why is there no such forest

Question

Let $ G = (V, E) $ be a graph such that $ |V| = |E| = 14 $. I need to prove $ G $ is not a forest. I tried showing that if $ |E| = 14 $, then the sum of all degress is $ 28 $ and therefore the degree of each $ vertex $ is at least $ 2 $, which means there is a cycle.

Answer 1

If you recall that for a (connected) tree, you have that $\vert V\vert-1=\vert E\vert$. Thus, if we have a forest with $n$ connected components (i.e. consisting of $n$ trees), it is seen that $\vert V\vert -n=\vert E\vert$. If a graph has $\vert V\vert=\vert E\vert$ then it is impossible for it to be a forest as there needs to be fewer edges than vertices (to even be a tree).

Answer 2

Your attempt doesn't work, unfortunately. We can say that the average degree of the vertices is exactly $2$, but this doesn't say much about the individual degrees. For example, if you take a cycle $C_{13}$, then add an extra vertex connected by a single edge to one of the vertices of $C_{13}$, you get a graph of $14$ vertices and edges, but where one of the vertices has degree $1$.

You can prove this by induction: show that if $G = (V, E)$ satisfies $|V| \le |E|$, then $G$ is not a forest. We proceed by induction on $|V|$, and prove it for $|V| \ge 3$ (otherwise we'd have to deal with repeated edges and/or loops).

For $|V| = 3$, then we have $3$ vertices and at least $3$ edges. Every graph on $3$ vertices has at most $\binom{3}{2} = 3$ edges, and the only graph with $3$ edges would be the complete graph $K_3$. This graph must be $G$. Note it is also a cycle, so it is not a forest.

Suppose $n \ge 3$ is such that no graph with $n$ vertices and at least $n$ edges is a forest. Suppose $G = (V, E)$ where $|V| = n + 1 \le |E|$. For the sake of contradiction, suppose $G$ is a forest.

If every vertex in $G$ had degree at least $2$, then $G$ contains a cycle, and hence is not a forest. Thus, $G$ contains a vertex of degree $1$ or $0$. Let $G' = (V', E')$ be the result of removing this vertex, and its incident edge (if it has one). Note that a single vertex was removed, so $|V'| = |V| - 1 = n$, and at most one edge was removed, so $|E'| \ge |E| - 1 \ge n$.

By our induction hypothesis, $G'$ must not be a forest, and hence contains a cycle. But, since $G$ is simply $G'$ with an extra vertex and possibly an extra edge, the cycle in $G'$ must also be contained in $G$, contradicting our assumption that $G$ is a forest.