# Is there any way to generate all the possible undirected graphs with unlabeled nodes?

I am looking for an efficient algorithm to generate all of the unique graphs for a given number of nodes.

For small instances, the total number of graphs are as follows:

n=2 G=2

n=3 G=4

n=4 G=11

n=5 G=34

I used the complementarity property of graphs to make it easier to enumerate all of them.

• What’s your question exactly? Are you asking for a way to do this? It seems you have a way in mind already. Jun 20, 2019 at 21:39
• I am looking for a method to track all the generated graphs. A simple algorithm is to generate all $2^{{n}\choose{2}}$ cases. But, as the number of nodes increases, the difference between the total number of unique graphs and that number super exponentially grows. I have some basic idea but for large n's it doesn't work since some weird cases happen. I wanted to realize whether there exists any method for it or not. The method should ensure that at each step we have a new graph. I am not sure but I think realizing the similarity of two unlabeled and undirected graphs is an NP-hard problem. Jun 21, 2019 at 1:44
• Maybe I am missing something obvious, but what is the connection to OR? this should be in the CS or math stackexchange. Jun 21, 2019 at 7:18
• @Michael Feldmeier Graph theory is part of/aplicable to OR. True it could be postedoin another SE site. But that is ture for almost every OR SE question. I take a big, flexible, and evolving tent view of OR, and apparently have a bigger and more flexible tent view of OR than you do (and not just based on this question).. Jun 21, 2019 at 11:52
• To me this question is on the borderline. I think math or CS might have been a better fit for this question, but I think it's close enough that I'm not planning to cast a close vote (or, probably, an open vote, if it gets closed). I think graph theory is close enough to OR (especially since there is an algorithmic aspect to this question) that it can be in scope. Jun 22, 2019 at 15:33

See http://oeis.org/A000088, which gives a different number (34) for n = 5.

• This seems more like a comment than an answer. OTOH the OP accepted it, so... Jun 22, 2019 at 15:35
• I think the link leads to a good source of materials for this question. Jun 23, 2019 at 15:57

There is a program that generates those graphs for the small number of vertices. http://users.cecs.anu.edu.au/~bdm/data/graphs.html

The following code converts the file with the g6 format to an array (it is written in python).

import numpy as np

file_contents = open("graph3c.txt", "r")

for line in lines:

n = ord(line.split()[0][0]) - 63
h = ''

l = n - 1
for i in range(1,l):
temp = bin(ord(line.split()[0][i])-63)[2:]
if len(temp) < 6:
for k in range(6 - len(temp)):
h = h + '0'
h = h + temp

A = [[0]*n for j in range(n)]
k = 0;
for i in range(1,n):
for j in range(0,i):
A[i][j] = int(h[k])
A[j][i] = A[i][j]
k = k+1

$$$$
`

I've seen several researchers using the NAUTY package to generate all graphs of a given size:

https://pallini.di.uniroma1.it/

The GraphsInGraphs contains a database of all undirected graphs with up to 10 nodes, and code to generate larger ones. One of the original goals was to detect sub-graphs and isomorphisms.

You can find the mathematical background here: https://www.gerad.ca/fr/papers/G-2016-10