TOPICS
Search

Null Graph


The term "null graph" is used both to refer to any empty graph and to the empty graph on 0 nodes.

Because of the conflicting usage, the term should be qualified. Harary and Read (1974, pp. 37-44) discuss the usefulness of the 0-node empty graph and the conventions needed to include it in graph theory. Whether it is considered connected or a tree depends on the chosen definitions.

The 0-node empty graph has a trivial automorphism group, consisting of the unique empty permutation. It has an empty graph embedding in the sphere, but this is not a cellular embedding, since the complement is the whole sphere rather than an open disk. The usual polyhedral formula therefore does not apply to that graph embedding.

McKay (2002) argues that the exceptions introduced by the 0-node empty graph make it preferable to exclude it, quipping that "the only good null graph is a dead null graph." This is a choice of convention rather than a statement that the graph does not exist.


See also

Complete Graph, Empty Graph, Singleton Graph

Explore with Wolfram|Alpha

References

Harary, F. and Read, R. C. "Is the Null-Graph a Pointless Concept?" In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin, Germany: Springer, pp. 37-44, 1974. https://doi.org/10.1007/BFb0066433.McKay, B. "RE: [Graphs with n Edges]." Sequence fans mailing list. 10 Oct 2002. https://groups.google.com/g/seqfan/.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 141, 1990.

Referenced on Wolfram|Alpha

Null Graph

Cite this as:

Weisstein, Eric W. "Null Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NullGraph.html

Subject classifications