# Null graph

(Redirected from Empty graph)

In the mathematical field of graph theory, the null graph may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an empty graph).

## Order-zero graph

Order-zero graph (null graph)
Vertices 0
Edges 0
Diameter 0
Girth $\infty$
Automorphisms 1
Chromatic number 0
Chromatic index 0
Genus 0
Properties Integral
Symmetric
Notation $K_0$

The order-zero graph $K_0$ is the unique graph of order zero (having zero vertices). As a consequence, it also has zero edges. In some contexts, $K_0$ is excluded from being considered a graph (either by definition, or more simply as a matter of convenience).

The order-zero graph is the initial object in the category of graphs, according to some definitions of a category of graphs. Its inclusion within the definition of graph theory is more useful in some contexts than others. On the positive side, $K_0$ follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair of empty sets), and in recursively defined data structures $K_0$ is useful for defining the base case for recursion (by treating the null tree as the child of missing edges in any non-null binary tree, every non-null binary tree has exactly two children). On the negative side, most well-defined formulas for graph properties must include exceptions for $K_0$ if it is included as a graph ("counting all strongly connected components of a graph" would become "counting all non-null strongly connected components of a graph"). Due to the undesirable aspects, it is usually assumed in literature that the term "graph" implies "graph with at least one vertex" unless context suggests otherwise.[1][2]

When acknowledged, $K_0$ fulfills (vacuously) most of the same basic graph properties as $K_1$ (the graph with one vertex and no edges): it has a size of zero, it is equal to its complement graph ($\bar K_0$), it is a connected component (namely, $\forall x \isin V : \forall y \isin V : \exists \text{path}(x,y)$), a forest, and a planar graph. It may be an undirected graph or a directed graph (or even both); when considered as directed, it is a directed acyclic graph, and it is both a complete graph and an empty graph (just to name a few). However, definitions for each of these graph properties will vary depending on whether context allows for $K_0$.

## Edgeless graph

Edgeless graph (empty graph, null graph)
Vertices n
Edges 0
Diameter 0
Girth $\infty$
Automorphisms n!
Chromatic number 1
Chromatic index 0
Genus 0
Properties Integral
Symmetric
Notation $\bar K_n$

For each natural number n, the edgeless graph (or empty graph) $\bar K_n$ is the graph with n vertices and zero edges. An edgeless graph is occasionally referred to as a null graph in contexts where the order-zero graph is not permitted.[3][4]

The n-vertex edgeless graph is the complement graph for the complete graph $K_n$, and therefore it is commonly denoted as $\bar K_n$.