Definition:Edgeless Graph

From ProofWiki
Jump to: navigation, search

Definition

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$.


Examples

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

NullGraphs.png


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.


Sources

Weisstein, Eric W. "Empty Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EmptyGraph.html