Generate all unlabelled simple graphs on a given number of vertices with various additional properties.
This is a website interface to the program geng, which is part of nauty, written by Brendan McKay.
The default output of nauty is the graph6 format, but on this website a number of more human-readable graph representations is also available.
Number $n$ of vertices
(max. 20)
Connected
Minimum number of edges
Biconnected
Maximum number of edges
Triangle-free
Minimum degree $\geq$
4-cycle-free
Maximum degree $\leq$
Bipartite
Canonic labeling
Graph format
Output format
Output
numbering
graphics
Object info
Graphs are among the most heavily studied objects in combinatorics.
However, despite their simple definition, they are much more complex than the basic objects like permutations, combinations, partitions etc.
Formally, a graph is a pair $G=(V,E)$, where $V$ is a finite nonempty set and $E$ is a set of unordered distinct pairs of elements from $V$, called the of vertices and edges of the graph, respectively.
To emphasize that loops and multiple edges are disallowed, such graph are sometimes called simple.
Here we consider graphs to be unlabelled, which means we consider them the same if they differ only in renaming of the vertices.
We write $n:=|V|$ for the number of vertices, and we always consider the vertex set $V=\{1,2,\ldots,n\}$ for simplicity.
Graphs can be represented in a computer in a variety of ways.
An edge list is a list of all edges of the graph.
Another representation is the adjacency list, which is a list that specifies for each vertex $i$ the list of all its neighbors, i.e., all edges $ij\in E$.
A graph can also be represented by its adjacency matrix, which is an $n\times n$ matrix $A$ with $a_{i,j}=1$ if $ij\in E$ and $a_{i,j}=0$ otherwise.
As we only consider undirected graphs, we always have $a_{i,j}=a_{j,i}$.
For example, consider the graph shown below.
Its edge list representation is 1,2; 1,3; 2,3; 2,4; 3,4, its adjacency list representation is 1[2 3] 2[1 3 4] 3[1 2 4] 4[2 3], and the adjacency matrix representation is 0110 1011 1101 0110 (written out row by row).
Enumeration (OEIS)
OEIS sequences related to unlabelled $n$-vertex graphs: