PROFILBARU.COM

Edgeless graph (empty graph, null graph)
Edgeless graph (empty graph, null graph)
Vertices	n
Edges	0
Radius	0
Diameter	0
Girth	∞
Automorphisms	n!
Chromatic number	1
Chromatic index	0
Genus	0
Properties	Integral; Symmetric
Notation	Kn
	Table of graphs and parameters

Order-zero graph (null graph)
Order-zero graph (null graph)
Vertices	0
Edges	0
Girth	∞
Automorphisms	1
Chromatic number	0
Chromatic index	0
Genus	0
Properties	Integral; Symmetric; Treewidth -1
Notation	K0
	Table of graphs and parameters

In the mathematical field of graph theory, the term "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

The order-zero graph, $K 0$ , is the unique graph having no vertices (hence its order is zero). It follows that $K 0$ also has no edges. Thus the null graph is a regular graph of degree zero. Some authors exclude $K 0$ from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including $K 0$ as a valid graph is useful depends on context. On the positive side, $K 0$ follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair $(V, E)$ for which the vertex and edge sets, $V$ and $E$ , are both empty), in proofs it serves as a natural base case for mathematical induction, and similarly, 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, including $K 0$ as a graph requires that many well-defined formulas for graph properties include exceptions for it (for example, either "counting all strongly connected components of a graph" becomes "counting all non-null strongly connected components of a graph", or the definition of connected graphs has to be modified not to include $K 0$ ). To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise.^[1]^[2]

In category theory, the order-zero graph is, according to some definitions of "category of graphs," the initial object in the category.

$K 0$ does fulfill (vacuously) most of the same basic graph properties as does $K 1$ (the graph with one vertex and no edges). As some examples, $K 0$ is of size zero, it is equal to its complement graph $K 0$ , a forest, and a planar graph. It may be considered undirected, directed, or even both; when considered as directed, it is a directed acyclic graph. And it is both a complete graph and an edgeless graph. However, definitions for each of these graph properties will vary depending on whether context allows for $K 0$ .

Edgeless graph

For each natural number $n$ , the edgeless graph (or empty graph) $K n$ of order $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.^[1]^[2]

It is a 0-regular graph. The notation $K n$ arises from the fact that the $n$ -vertex edgeless graph is the complement of the complete graph $K n$ .

Notes

^ ^a ^b Weisstein, Eric W. "Empty Graph". MathWorld.
^ ^a ^b Weisstein, Eric W. "Null Graph". MathWorld.

References

Harary, F. and Read, R. (1973), "Is the null graph a pointless concept?", Graphs and Combinatorics (Conference, George Washington University), Springer-Verlag, New York, NY.