The graph isomorphism problem is known to be NP-complete, so any sort of properties that distinguish graphs is likely to be hard to compute.

Are you sure of this? Eric Weisstein's World of Mathematics, at http://mathworld.wolfram.com/GraphIsomorphismComplete.html, says ______________________________________________________ Graph Isomorphism Complete There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete. In fact, the problem of identifying isomorphic graphs seems to fall in a crack between P and NP-complete, if such a crack exists (Skiena 1990, p. 181), and as a result, the problem is sometimes assigned to a special graph isomorphism complete complexity class. References Skiena, S. "Graph Isomorphism." 5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 181-187, 1990. _______________________________________________________ Was there a recent result that didn't make it into World of Mathematics showing that Graph Isomorphism is NP complete? The fact that graph isomorphism "seems to" not be in P means that no-one has yet found a set of simple, easy-to-compute properties that will distinguish graphs. That doesn't mean that some clever person won't find such a set in the future, showing graph isomorphism to be in P in the process (and doing this won't show that P=NP). Andy Latto andy.latto@pobox.com