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
![Z(S_p^((2)))=1/(p!)sum_((j))h_(j)product_(n=0)^(|_(p-1)/2_|)a_(2n+1)^(nj_(2n+1)+(2n+1)(j_(2n+1); 2))product_(n=1)^(|_p/2_|)[(a_na_(2n))^(n-1)]^(j_(2n))a_(2n)^(2n(j_(2n); 2))product_(q=1)^pproduct_(r=q+1)^pa_(LCM(q,r))^(j_qj_rGCD(q,r))](/images/equations/SimpleGraph/NumberedEquation4.svg) |
(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.
