# Graphs

This page contains some collections of graphs. See the combinatorial data page concerning data formats.

## Simple graphs

2 vertices: all (2)   connected (1)
3 vertices: all (4)   connected (2)
4 vertices: all (11)   connected (6)
5 vertices: all (34)   connected (21)
6 vertices: all (156)   connected (112)
7 vertices: all (1044)   connected (853)
8 vertices: all (12346)   connected (11117)
9 vertices: all (274668)   connected (261080)
10 vertices: all (31MB gzipped) (12005168)   connected (30MB gzipped) (11716571)

The above graphs, and many varieties of them, can be efficiently generated using the program geng.

A table giving the number of graphs according to the number of edges and vertices, up to 16 vertices, can be found here.

## Eulerian graphs

Here we give the small simple graphs with every degree even.

2 vertices: all (1)
3 vertices: all (2)   connected (1)
4 vertices: all (3)   connected (1)
5 vertices: all (7)   connected (4)
6 vertices: all (16)   connected (8)
7 vertices: all (54)   connected (37)
8 vertices: all (243)   connected (184)
9 vertices: all (2038)   connected (1782)
10 vertices: all (33120)   connected (31026)
11 vertices: all (1182004)   connected (1148626)
12 vertices: part 1part 2part 3part 4;  (each file about 81MB) (87723296)

## Strongly regular graphs

SRG(25,8,3,2) (1 graph)
SRG(25,12,5,6) (15 graphs)
SRG(26,10,3,4) (10 graphs)
SRG(27,10,1,5) (1 graph)
SRG(28,12,6,4) (4 graphs)
SRG(29,14,6,7) (41 graphs)
SRG(35,16,6,8) (3854 graphs)
SRG(35,18,9,9) (227 graphs)
SRG(36,14,4,6) (180 graphs)
SRG(36,15,6,6) (32548 graphs, gzipped). These come in 227 switching classes, one for each regular two-graph of order 36. We also provide one representative of each class.
SRG(37,18,8,9) (6760 graphs, maybe incomplete)
SRG(40,12,2,4) (28 graphs)

## Ramsey graphs

A Ramsey(s,t)-graph is a graph with no clique of size s, and no independent set of size t. On the Ramsey graph page we present some of these graphs.

## Hypohamiltonian graphs

A graph is hypohamiltonian if it is not Hamiltonian but each graph that can be formed from it by removing one vertex is Hamiltonian. The smallest is the Petersen graph. The following are all hypohamiltonian graphs with fewer than 18 vertices, and a selection of larger hypohamiltonian graphs.

10 vertices (1 graph)
13 vertices (1 graph)
15 vertices (1 graph)
16 vertices (4 graphs)
18 vertices (13 graphs, maybe incomplete)
22 vertices (10 graphs, maybe incomplete)
26 vertices (2033 graphs, maybe incomplete)

In the case of hypohamiltonian cubic graphs we can give a complete catalogue to a larger size. Up to 26 vertices inclusive we give all of them. For 28 vertices we give those with girth at least 5, and for 30 vertices girth at least 6.

10 vertices (1 graph)
18 vertices (2 graphs)
20 vertices (1 graph)
22 vertices (3 graphs)
24 vertices (1 graph)
26 vertices (100 graphs)
28 vertices (34 graphs)
30 vertices (1 graph)

## Planar graphs

Here are give some non-isomorphic connected planar graphs. Isomorphism is according to the combinatorial structure regardless of embeddings. If you are looking for planar graphs embedded in the plane in all possible ways, your best option is to generate them using plantri.

1 vertex (1 graph)
2 vertices (1 graph)
3 vertices (2 graphs)
4 vertices (6 graphs)
5 vertices (20 graphs)
6 vertices (99 graphs)
7 vertices (646 graphs)
8 vertices (5974 graphs)
9 vertices (71885 graphs)
10 vertices (gzipped) (1052805 graphs)
11 vertices (gzipped) Part A  Part B  (17449299 graphs)

## Semiregular bipartite graphs

On the semiregular page we provide many counts of labelled semiregular bipartite graphs.

## Self-complementary graphs

A self-complementary graph is one isomorphic to its complement. Such graphs can only have orders congruent to 0 or 1 modulo 4.

4 vertices (1 graph)
5 vertices (2 graphs)
8 vertices (10 graphs)
9 vertices (36 graphs)
12 vertices (720 graphs)
13 vertices (5600 graphs)
16 vertices (gzipped) (703760 graphs)
17 vertices (gzipped) Part A  Part B  Part C  (11220000 graphs)
20 vertices (incomplete, gzipped) Part A  Part B  Part C  Part D  (8571844 graphs)

The 20-vertex graphs provided are those which have a complementing permutation of order 8 or 16. There is a much larger number of graphs with complementing permutations of order 4. The total count for order 20 is 9168331776, which is too many to present here. The number of self-complementary graphs of order 21 is 293293716992.

## Highly irregular graphs

A connected graph is highly irregular if the neighbours of each vertex have distinct degrees. Such graphs exist on all orders except 3, 5 and 7.

1 vertex (1 graph)
2 vertices (1 graph)
4 vertices (1 graph)
6 vertices (1 graph)
8 vertices (3 graphs)
9 vertices (3 graphs)
10 vertices (13 graphs)
11 vertices (21 graphs)
12 vertices (110 graphs)
13 vertices (474 graphs)
14 vertices (2545 graphs)
15 vertices (18696 graphs)

Page Master: Brendan McKay, bdm@cs.anu.edu.au and http://cs.anu.edu.au/~bdm.

Up to the combinatorial data page