Editing Null graph

{{Short description|Order-zero graph or any edgeless graph}}
In the [[mathematics|mathematical]] field of [[graph theory]], the term "'''null graph'''" may refer either to the [[order (graph theory)|order]]-[[zero]] [[graph (discrete mathematics)|graph]], or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").

==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 graph|Integral]]<br>[[Symmetric graph|Symmetric]]<br>[[Treewidth]] -1
}}

The '''order-zero graph''', {{math|''K''{{sub|0}}}}, is the unique graph having no [[vertex (graph theory)|vertices]] (hence its order is zero).  It follows that {{math|''K''{{sub|0}}}} also has no [[edge (graph theory)|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 theory|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 set|empty]]), in [[proof (mathematics)|proofs]] it serves as a natural base case for [[mathematical induction]], and similarly, in [[recursive definition|recursively defined]] [[data structure]]s {{math|''K''{{sub|0}}}} is useful for defining the base case for recursion (by treating the '''null [[tree (data structure)|tree]]''' as the [[child node (of a tree)|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 component]]s 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 ([[vacuous truth|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 (graph theory)|size]] zero, it is equal to its [[complement graph]] {{math|{{overline|''K''}}{{sub|0}}}}, a [[forest (graph theory)|forest]], and a [[planar graph]]. It may be considered [[undirected graph|undirected]], [[directed graph|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 graph|Integral]]<br>[[Symmetric graph|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|regular]] graph. The notation {{mvar|{{overline|K}}{{sub|n}}}} arises from the fact that the {{mvar|n}}-vertex edgeless graph is the [[complement graph|complement]] of the [[complete graph]] {{mvar|K{{sub|n}}}}.

==See also==

* [[Glossary of graph theory]]
* [[Cycle graph]]
* [[Path graph]]

==Notes==
{{reflist}}

==References==
{{refbegin}}
* [[Frank Harary|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]]