Small Graphs

This site is intended to collate much of the data about small graphs that I have to keep on recomputing. It is primarily designed for my own use, but anyone else is free to check out the numbers or the graphs. If you are interested in small graph data that is not here, then feel free to mail me at gordon@cs.uwa.edu.au because I may have just not got around to installing it.

Table of Contents

• Numbers of graphs
• Numbers of bipartite graphs
• Trees on up to 20 vertices
• Colourings of small graphs
• Class 2 graphs

Numbers of graphs

The exact numbers of graphs on n vertices and e edges can be computed by using Polya enumeration theory. This enables us to produce a series of tables of the following format. The tables were produced by a Maple program written with Brendan McKay (well, he wrote it after joint discussions).

Tables of this nature are available for the graphs on 1-16 vertices.

Bipartite graph

The following table gives the number of connected bipartite graphs separated according to the size of the bipartition. Each row corresponds to a fixed number of vertices, while each column refers to the smaller part of the bipartition. Thus the entry 34 for 7 vertices and m=3 indicates that there are 34 conected bipartite graphs on 7 vertices with partition of size (3,4).

Note that the second column 2,4,6,9 ... is the sequence A002620 in the Encylopaedia of Integer Sequences.

Trees on up to 16 vertices

The following table allows you to download all the trees on up to 16 vertices. As usual, they are in graph6 format.

Colourings of small graphs

The chromatic number of a graph is the smallest number k such that each vertex can be assigned a "colour" from the set {1,2,...,k} in such a fashion that the two ends of every edge are differently coloured.

The following table lists the chromatic numbers of all the connected graphs on up to 11 vertices.

Vertex-critical graphs

A graph is said to be vertex-critical if its chromatic number drops whenever a vertex is deleted.

The following table lists the number of vertex-critical graphs on up to 11 vertices. Each number is a link to the gzip-compressed file containing those graphs in graph6 format. In the larger files the 11-vertex graphs occupy about 2.7 bytes of space per graph. There have been some strange downloading idiosyncrasies that you may wish to consider before downloading.

Edge-critical graphs

A graph is said to be edge-critical if its chromatic number drops whenever an edge is deleted. Every edge-critical graph is necessarily vertex-critical.

The following table lists the number of edge-critical graphs on up to 12 vertices. Each number is a link to the file containing those graphs in graph6 format. In the larger files the 11-vertex graphs occupy an average of 4.1 bytes per graph. There have been some strange downloading idiosyncrasies that you may wish to consider before downloading.

Number of edges in critical graphs

One question in the structure theory of (edge-)critical graphs is the possible number of edges in a k-critical graph.

The next four tables give the values for the 4, 5, 6 and 7 critical graphs - each entry of the form 15 (6) indicates that there are 6 graphs on 15 edges.

Class 2 graphs

Vizing's theorem states that a graph can be edge-coloured in either d or d+1 colours, where d is the maximum degree of the graph. This partitions graphs into two classes, with the ones requiring d+1 colours known as class 2 graphs. Such luminaries as the Petersen] graph are class 2.

The following table gives the number of class 2 graphs from 4 to 9 vertices. The links provide the actual class 2 graphs in graph6 format.