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 graph with multiple edges is sometimes called a multigraph (Skiena 1990, p. 89).
The numbers of nonisomorphic simple graphs on 
nodes
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 up to 
vertices are 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.
An unweighted undirected graph may be tested in the Wolfram Language to see if it is a simple graph using SimpleGraphQ[g].
 |
(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)))=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 cycle
indices 
are
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
 |  |  |
(9)
|
Letting 
then gives 
,
the first few of which are
 |  |  |
(10)
| ||
 |  |  |
(11)
| ||
 |  |  |
(12)
| ||
 |  |  |
(13)
| ||
 |  |  |  |  |
(14)
|
Plugging in 
to any of these gives the total number of simple graphs on 
nodes. 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.
