Null graph


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.

Order-zero graph

The order-zero graph,, is the unique graph having no vertices. It follows that also has no edges. Thus the null graph is a regular graph of degree zero. Some authors exclude from consideration as a graph. Whether including as a valid graph is useful depends on context. On the positive side, follows naturally from the usual set-theoretic definitions of a graph, in proofs it serves as a natural base case for mathematical induction, and similarly, in recursively defined data structures is useful for defining the base case for recursion. On the negative side, including as a graph requires that many well-defined formulas for graph properties include exceptions for it. 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.
In category theory, the order-zero graph is, according to some definitions of "category of graphs," the initial object in the category.
does fulfill most of the same basic graph properties as does . As some examples, is of size zero, it is equal to its complement graph, 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.

Edgeless graph

For each natural number n, the edgeless graph 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.
It is a 0-regular graph. The notation arises from the fact that the n-vertex edgeless graph is the complement of the complete graph.