next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
NautyGraphs :: Example: Checking for isomorphic graphs

Example: Checking for isomorphic graphs

The main use of nauty is to determine if two graphs are isomorphic. We can demonstrate it for two given graphs with the method areIsomorphic.
G = graph {{1,2},{2,3},{3,4},{4,5},{1,5}};
H = graph {{1,3},{3,5},{5,2},{2,4},{4,1}};
areIsomorphic(G, H)
Further, a list of graphs can be reduced to only graphs that are non-isomorphic with the method removeIsomorphs. Here we create a list of 120 different labellings of the 5-cycle and use nauty to verify they are indeed all the same.
L = graphToString \ apply(permutations 5, P -> graph apply(5, i -> {P_i, P_((i+1)%5)}));
N = removeIsomorphs L
stringToGraph first N

See also