0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Excellent! Thank you. $\endgroup$ – YoTengoUnLCD Dec 15 '15 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.