Definition:Edgeless Graph

From ProofWiki
Jump to navigation Jump to search


An edgeless graph is a graph with no edges.

That is, an edgeless graph is a graph of size zero.

Equivalently, an edgeless graph is a graph whose vertices are all isolated.

The edgeless graph of order $n$ is denoted $N_n$.


The edgeless graphs of order $1$ to $5$ are illustrated below:


Also known as

This is sometimes called an empty graph

Thus the term $n$-empty graph can often be seen for $N_n$.

The symbol $\overline K_n$ is frequently used to denote the $n$-empty graph, which follows from Empty Graph is Complement of Complete Graph.

The term null graph can also be found, but this can be confused with the graph with no vertices.

Also see

  • The edgeless graph $N_n$ has $n$ components for all $n$.
  • $N_1$ is a tree while for all $n > 1$, $N_n$ is a forest.


Weisstein, Eric W. "Empty Graph." From MathWorld--A Wolfram Web Resource.