Every simple graph has at least $n-k$ edges.

Question

From here on, $n$ will denote the number of vertices and $k$ will denote the number of connected components of the graph in question.

Theorem.

Let $F$ be a forest, then $F$ has $n-k$ edges.

Proof.

Every connected component of $F$ is a tree, and as trees are planar, $F$ is planar. Then we can apply Euler's formula: $n-e+f=1+k$.

As $F$ has no cycles, we have that $f=1$ and thus $e=n-k$.

Until here I understand everything, but the following in troubling me.

Corollary

It follows that every simple graph has at least $n-k$ vertices.

How does that follow from the theorem above?

Answer 1

It follows from the fact that every simple graph has a spanning forest (i.e. a spanning tree on every connected component). Pick one spanning forest and count the number of edges there. The original graph cannot have fewer edges than the spanning forest.