Edgeless Graph of Order Greater than 1 is Forest

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $N_n$ denote the edgeless graph with $n$ vertices such that $n > 1$.

Then $N_n$ is a forest.


Proof

By definition, a forest is a simple graph whose components are all trees.

From Edgeless Graph of Order n has n Components $N_n$ has as many components as it has vertices.

Each of those vertices is an instance of $N_1$, the edgeless graph with $1$ vertex.

The result follows from Edgeless Graph of Order 1 is Tree.

$\blacksquare$