# 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 '19 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 '19 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 '19 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 '19 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 '19 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 '19 at 15:35
• I think the link leads to a good source of materials for this question. Jun 23 '19 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()) - 63
h = ''

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

A = [*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