Null graph
Template:Short description 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
<templatestyles src="Infobox graph/styles.css"/>Script error: No such module "Infobox".Template:Template other
The order-zero graph, K0Script error: No such module "Check for unknown parameters"., is the unique graph having no vertices (hence its order is zero). It follows that K0Script error: No such module "Check for unknown parameters". also has no edges. Thus the null graph is a regular graph of degree zero. Some authors exclude K0Script error: No such module "Check for unknown parameters". from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including K0Script error: No such module "Check for unknown parameters". as a valid graph is useful depends on context. On the positive side, K0Script error: No such module "Check for unknown parameters". follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair (V, E)Script error: No such module "Check for unknown parameters". for which the vertex and edge sets, Template:Mvar and Template:Mvar, are both empty), in proofs it serves as a natural base case for mathematical induction, and similarly, in recursively defined data structures K0Script error: No such module "Check for unknown parameters". 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 K0Script error: No such module "Check for unknown parameters". 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 K0Script error: No such module "Check for unknown parameters".). 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.[2][3]
In category theory, the order-zero graph is, according to some definitions of "category of graphs," the initial object in the category.
K0Script error: No such module "Check for unknown parameters". does fulfill (vacuously) most of the same basic graph properties as does K1Script error: No such module "Check for unknown parameters". (the graph with one vertex and no edges). As some examples, K0Script error: No such module "Check for unknown parameters". is of size zero, it is equal to its complement graph K0Script error: No such module "Check for unknown parameters"., 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 K0Script error: No such module "Check for unknown parameters"..
Edgeless graph
<templatestyles src="Infobox graph/styles.css"/>Script error: No such module "Infobox".Template:Template other
For each natural number Template:Mvar, the edgeless graph (or empty graph) Template:Mvar of order Template:Mvar is the graph with Template:Mvar 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.[2][3]
It is a 0-regular graph. The notation Template:Mvar arises from the fact that the Template:Mvar-vertex edgeless graph is the complement of the complete graph Template:Mvar.
See also
Notes
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".
References
<templatestyles src="Refbegin/styles.css" />
- 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.