A mathematical object composed of points known as Vertices or Nodes and lines connecting some (possibly empty) Subset of them, known as Edges. The study of graphs is known as Graph Theory. Graphs are 1-D Complexes, and there are always an Even number of Odd Nodes in a graph. The number of nonisomorphic graphs with Nodes is given by the Pólya Enumeration Theorem. The first few values for , 2, ..., are 1, 2, 4, 11, 34, 156, 1044, ... (Sloane's A000088; see above figure).

Graph sums, differences, powers, and products can be defined, as can graph eigenvalues.

Before applying Pólya Enumeration Theorem, define the quantity

(1) |

(2) |

(3) |

(4) | |

(5) | |

(6) |

(7) |

(8) | |||

(9) | |||

(10) | |||

(11) | |||

(12) | |||

(13) |

Application of the Pólya Enumeration Theorem then gives the formula

(14) |

(15) | |||

(16) | |||

(17) | |||

(18) | |||

(19) | |||

(20) |

Letting then gives a Polynomial , which is a Generating Function for (i.e., the terms of
give) the number of graphs with Edges. The total number of graphs having edges is .
The first few are

(21) | |||

(22) | |||

(23) | |||

(24) | |||

(25) | |||

(26) |

giving the number of graphs with nodes as 1, 2, 4, 11, 34, 156, 1044, ... (Sloane's A000088). King and Palmer (cited in Read 1981) have calculated up to , for which

(27) |

**References**

Bogomolny, A. ``Graph Puzzles.'' http://www.cut-the-knot.com/do_you_know/graphs2.html.

Fujii, J. N. *Puzzles and Graphs.* Washington, DC: National Council of Teachers, 1966.

Harary, F. ``The Number of Linear, Directed, Rooted, and Connected Graphs.'' *Trans. Amer. Math. Soc.* **78**, 445-463, 1955.

Pappas, T. ``Networks.'' *The Joy of Mathematics.*
San Carlos, CA: Wide World Publ./Tetra, pp. 126-127, 1989.

Read, R. ``The Graph Theorists Who Count--and What They Count.'' In *The Mathematical Gardner*
(Ed. D. Klarner). Boston, MA: Prindle, Weber, and Schmidt, pp. 326-345, 1981.

Sloane, N. J. A. Sequence
A000088/M1253
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in
Sloane, N. J. A. and Plouffe, S.
*The Encyclopedia of Integer Sequences.* San Diego: Academic Press, 1995.

© 1996-9

1999-05-25