The empty graph on 0 nodes. Use of the null graph is discouraged since it is felt by many in the graph theoretical community that allowing the null graph causes much more trouble than it is worth (Harary and Read 1973). For example, the null graph has no automorphism group, it cannot be imbedded on the sphere obeying the polyhedral formula, it is connected and acyclic but has too many edges to be a tree, and so on. According to Brendan McKay (2002), it is an exception to so many things that the community (or most of it) has decided that the only good null graph is a dead null graph.

Harary, F. and Read, R. "Is the Null Graph a Pointless Concept?" In Graphs and Combinatorics Conference, George Washington University. New York: Springer-Verlag, 1973.

McKay, B. "RE: [Graphs with n Edges]." seqfan@ext.jussieu.fr mailing list. 10 Oct 2002.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 141, 1990.

CITE THIS AS:

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