Null graph

{{Short description|Order-zero graph or any edgeless 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 (the latter is sometimes called an "empty graph").

thumb|<ref name="r166">{{cite book | last1=Harary | first1=Frank | last2=Read | first2=Ronald C. | title=Graphs and Combinatorics | chapter=Is the null-graph a pointless concept? | publisher=Springer Berlin Heidelberg | publication-place=Berlin, Heidelberg | volume=406 | date=1974 | isbn=978-3-540-06854-9 | doi=10.1007/bfb0066433 | url=http://link.springer.com/10.1007/BFb0066433 | access-date=2025-10-26 | page=37–44}}</ref>

==Order-zero graph== {{infobox graph | name = Order-zero graph (null graph) | vertices = 0 | edges = 0 | girth = ∞ | automorphisms = 1 | chromatic_number = 0 | chromatic_index = 0 | genus = 0 | spectral_gap = ''undefined'' | notation = {{math|''K''{{sub|0}}}} | properties = Integral<br>Symmetric<br>Treewidth -1 }}

The '''order-zero graph''', {{math|''K''{{sub|0}}}}, is the unique graph having no vertices (hence its order is zero). It follows that {{math|''K''{{sub|0}}}} also has no edges. Thus the null graph is a regular graph of degree zero. Some authors exclude {{math|''K''{{sub|0}}}} from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including {{math|''K''{{sub|0}}}} as a valid graph is useful depends on context. On the positive side, {{math|''K''{{sub|0}}}} follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair {{math|(''V'', ''E'')}} for which the vertex and edge sets, {{mvar|V}} and {{mvar|E}}, are both empty), in proofs it serves as a natural base case for mathematical induction, and similarly, in recursively defined data structures {{math|''K''{{sub|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 {{math|''K''{{sub|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 {{math|''K''{{sub|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.<ref name="mathworld emptygraph">{{MathWorld |urlname=EmptyGraph |title=Empty Graph}}</ref><ref name="mathworld nullgraph">{{MathWorld |urlname=NullGraph |title=Null Graph}}</ref>

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

{{math|''K''{{sub|0}}}} does fulfill (vacuously) most of the same basic graph properties as does {{math|''K''{{sub|1}}}} (the graph with one vertex and no edges). As some examples, {{math|''K''{{sub|0}}}} is of size zero, it is equal to its complement graph {{math|{{overline|''K''}}{{sub|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 {{math|''K''{{sub|0}}}}.

==Edgeless graph== {{infobox graph | name = Edgeless graph (empty graph, null graph) | vertices = {{mvar|n}} | edges = 0 | radius = 0 | diameter = 0 | girth = ∞ | automorphisms = {{math|''n''!}} | chromatic_number = 1 | chromatic_index = 0 | genus = 0 | spectral_gap = ''undefined'' | notation = {{mvar|{{overline|K}}{{sub|n}}}} | properties = Integral<br>Symmetric |Degree=0}}

For each natural number {{mvar|n}}, the '''edgeless graph''' (or empty graph) {{mvar|{{overline|K}}{{sub|n}}}} of order {{mvar|n}} is the graph with {{mvar|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.<ref name="mathworld emptygraph"/><ref name="mathworld nullgraph"/>

It is a 0-regular graph. The notation {{mvar|{{overline|K}}{{sub|n}}}} arises from the fact that the {{mvar|n}}-vertex edgeless graph is the complement of the complete graph {{mvar|K{{sub|n}}}}.

==Notes== {{reflist}}

==References== {{refbegin}} * 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. {{refend}}

==External links== * {{cci|Null graphs}}

Category:Graph families Category:Regular graphs