# Graphs

This page contains some collections of graphs. See the data formats page for how to use them.

## 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)
11 vertices: all (2514MB gzipped) (1018997864)

Next we give simple graphs by their number of edges, not allowing isolated vertices but allowing disconnected graphs.

1 edge (1)
2 edges (2)
3 edges (5)
4 edges (11)
5 edges (26)
6 edges (68)
7 edges (177)
8 edges (497)
9 edges (1476)
10 edges (4613)
11 edges (15216)
12 edges (52944)
13 edges (193367)
14 edges (740226)
15 edges (2960520)
16 edges (12334829)
17 edges (53394755, gzipped)

Next we give simple connected graphs by their number of edges.

1 edge (1)
2 edges (1)
3 edges (3)
4 edges (5)
5 edges (12)
6 edges (30)
7 edges (79)
8 edges (227)
9 edges (710)
10 edges (2322)
11 edges (8071)
12 edges (29503)
13 edges (112822)
14 edges (450141)
15 edges (1867871)
16 edges (8037472)
17 edges (35787667, gzipped)
18 edges (164551477, gzipped)

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 30 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)

## Chordal graphs

A graph is chordal if every cycle of length at least 4 has a chord. Here are some files of connected chordal graphs.

4 vertices (5)
5 vertices (15)
6 vertices (58)
7 vertices (272)
8 vertices (1614)
9 vertices (11911)
10 vertices (109539)
11 vertices (1247691)
12 vertices (17566431, gzipped)
13 vertices (305310547, gzipped)

## Perfect graphs

A graph is perfect if every odd cycle of length at least 5 has a chord, and the same is true of the complement graph. Here are some files of perfect graphs.

5 vertices (33)
6 vertices (148)
7 vertices (906)
8 vertices (8887)
9 vertices (136756)
10 vertices (3269264)
11 vertices (115811998, gzipped)

## Strongly regular graphs

Here are some strongly regular graphs made by myself and/or Ted Spence and/or someone else. More information and more graphs can be found on Ted's strongly-regular page.

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)
SRG(65,32,15,16) (32 graphs, maybe incomplete). The existence was an open problem for a long time until Oleg Gritsenko found one. We have expanded the set to 32 graphs but there may be more.

## 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)

Also see the Plane graphs page.

## 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)

## Edge-critical graphs

We will call an undirected simple graph G with no isolated vertices edge-k-critical if it has chromatic number k and, for every edge e, G-e has chromatic number k-1. It is easy to check that G must be connected.

The following graphs were generated by Olivier Lalonde. Olivier's code can be found on Github. Files with more than a million graphs are gzipped.

k
n 4 5 6 7 8 9 10 11 12 13
4 1
5 0 1
6 1 0 1
7 2 1 0 1
8 5 2 1 0 1
9 21 21 2 1 0 1
10 150 162 22 2 1 0 1
11 1221 4008 393 22 2 1 0 1
12 14581 147753 17036 395 22 2 1 0 1
13 207969 8311809 1479809 25355 395 22 2 1 0 1
14 3567180

## Circulant graphs

A graph with vertices 0,1,...,n-1 is circulant if the permutation (0,1,...,n-1) is an automorphism. In the following gzipped tar files are text files with names of the form circ<n>.<d>.txt containing the circulant graphs with n vertices and degree d. Each graph is given on one line as a set S of d integers. The vertices are 0,1,...,n-1 and the edges are all pairs {x,y} where xy is in S modulo n.

All degrees (up to complement) are present up to 60 vertices, then degrees at most 20 up to 65 vertices, at most 16 up to 70 vertices and at most 12 up to 100 vertices.

Page Master: Brendan McKay, brendan.mckay@anu.edu.au and https://users.cecs.anu.edu.au/~bdm.

Up to the combinatorial data page