The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

NAUTY -- Graph Isomorphism

The world's fastest isomorphism testing program is Nauty, by Brendan D. McKay. Nauty (No AUTomorphisms, Yes?) is a set of very efficient C language procedures for determining the automorphism group of a vertex-colored graph. It provides this information in the form of a set of generators, the size of group, and the orbits of the group. Nauty is also able to produce a canonically-labeled isomorph of the graph, to assist in isomorphism testing. It was the basis of the first program to generate all the 11-vertex graphs without isomorphs, and can test most graphs of less than 100 vertices in well under a second. Nauty has been successfully ported to a variety of operating systems and C compilers. It may be obtained from It is free for educational and research applications, but for commercial use contact the author at
  • Download Files (local site)
  • Brendan McKay's Page
  • Offical site

    Problem Links

    Graph Isomorphism (10)
    Generating Graphs (7)

    This page last modified on 2008-07-10 .