Simple Graph

A simple graph, also called a strict graph (Tutte 1998, p. 2), is an unweighted, undirected graph containing no graph loops or multiple edges (Gibbons 1985, p. 2; West 2000, p. 2; Bronshtein and Semendyayev 2004, p. 346). A simple graph may be either connected or disconnected.

Unless stated otherwise, the unqualified term "graph" usually refers to a simple graph. A simple graph with multiple edges is sometimes called a multigraph (Skiena 1990, p. 89).

The number of nonisomorphic simple graphs on nodes can be given by NumberOfGraphs[n] in the Wolfram Language package Combinatorica` , and the values for , 2, ... are 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ... (OEIS A000088; see above figure). King and Palmer (cited in Read 1981) have calculated up to , for which

(1)

There appears to be no standard term for a simple graph on edges, although the words "polynema" (Kyrmse) and "polyedge" (Muñiz 2011) have been proposed for -edge connected graphs.

All simple graphs on nodes can be enumerated using ListGraphs[n] in the Wolfram Language package Combinatorica` and a precomputed list on up to vertices is available via GraphData[n]. A much more efficient enumeration can be done using the program geng (part of nauty) by B. McKay. However, since the order in which graphs are returned by the geng program changes as a function of time as improvements are made, the canonical ordering given on McKay's website is used here and in GraphData.

A graph may be tested in the Wolfram Language to see if it is a simple graph using SimpleGraphQ[g].

A polynomial

(2)

that enumerates the number of distinct graphs with nodes (where is the number of graphs on nodes with edges) can be found using a rather complicated application of the Pólya enumeration theorem. This procedure gives the counting polynomial as

(3)

where is the pair group that acts on the 2-subsets of , which is given by

(4)

(Harary 1994, p. 185). Here, is the floor function, is a binomial coefficient, LCM is the least common multiple, GCD is the greatest common divisor, the sum is over all exponent vectors of the cycle index of the symmetric group , and is the coefficient of the term with exponent vector in . The first few cyclic indices are

			(5)
			(6)
			(7)
			(8)
			(9)

These can be given by the command PairGroup[SymmetricGroup[n]], x] in the Wolfram Language package Combinatorica` . Normalizing by and letting then gives , the first few of which are

			(10)
			(11)
			(12)
			(13)
			(14)

These polynomials are implemented as GraphPolynomial[n, x] in the Wolfram Language package Combinatorica` .

Plugging in to any of these gives the total number of simple graphs on nodes. All simple graphs on nodes with edges can be enumerated using the command ListGraphs[n, k] in the Wolfram Language package Combinatorica` . The number of nonisomorphic simple graphs on nodes with edges can be given by NumberOfGraphs[n, k] in the Wolfram Language package Combinatorica` , The array for the number of graphs having nodes and edges is given below (OEIS A008406).

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1
2	1	1
3	1	1	1	1
4	1	1	2	3	2	1	1
5	1	1	2	4	6	6	6	4	2	1	1
6	1	1	2	5	9	15	21	24	24	21	15	9	5	2	1	1

The mean number of edges for graphs with vertices is given by , giving the sequence for , 2, ... of 0, 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, ... (OEIS A064038 and A014695). This means that the total number of edges in the distinct graphs of orders , 2, ... are 0, 1, 6, 33, 170, 1170, 10962, 172844, 4944024, 270116280, ... (OEIS A086314).

The figure above shows the first few members of various common classes of simple graphs: the antiprism graph, complete graph, cycle graph, empty graph, gear graph, prism graph, star graph, and wheel graph.