Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a combination of the two I listed will fail to distinguish between two random trees of the same size with high probability.
Is there a known set of graph invariants that does always distinguish between non-isomorphic graphs? To rule out trivial examples, I'll require that the problem of comparing two such invariants is in P (or at the very least, not obviously equivalent to graph isomorphism) — so, for instance, "the adjacency matrix" is not a good answer. (Computing the invariants is allowed to be hard, though.)
If this is (as I sort of suspect) in fact open, does anyone have any insight on why it should be hard? Such a set of invariants wouldn't require or violate any widely-believed complexity-theoretic conjectures, and actually there are complexity-theoretic reasons to think that something like it exists (specifically, under derandomization, graph isomorphism is in co-NP). It seems like it shouldn't be all that hard…
Edit: Thorny's comment raises a good point. Yes, there is trivially a complete graph invariant, which is defined by associating a unique integer (or polynomial, or labeled graph…) to every isomorphism class of graphs. Since there are a countable number of finite graphs, we can do this, and we have our invariant.
This is logically correct but not very satisfying; it works for distinguishing between finite groups, say, or between finite hypergraphs or whatever. So it doesn't actually tell us anything at all about graph theory. I'm not sure if I can rigorously define the notion of a "satisfying graph invariant," but here's a start: it has to be natural, in the sense that the computation/definition doesn't rely on arbitrarily choosing an element of a finite set. This disqualifies Thorny's solution, and I think it disqualifies Mariano's, although I could be wrong.
Best Answer
A complete graph invariant is computationally equivalent to a canonical labeling of a graph. A canonical labeling is by definition an enumeration of the vertices of every finite graph, with the property that if two graphs are isomorphic as unlabeled graphs, then they are still isomorphic as labeled graphs. If you have a black box that gives you a canonical labeling, then obviously that is a complete graph invariant. On the other hand, if you have a complete graph invariant for unlabeled graphs, then you also have one for partially labeled graphs. So given a black box that computes a complete graph invariant, you can assign the label 1 to the vertex that minimizes the invariant, then assign a label 2 to a second vertex than again minimizes the invariant, and so on.
There are algorithms to decide graph isomorphism for certain types of graphs, or for all graphs but with varying performance, and there are algorithms for canonical labeling, again with varying performance. It is understood that graph isomorphism reduces to canonical labeling, but not necessarily vice versa. The distinction between the two problems is discussed in this classic paper by Babai and Luks.
One natural canonical labeling of a graph is the one that is lexicographically first. I think I saw, although I don't remember where, a result that computing this canonical labeling for one of the reasonable lex orderings on labeled graphs is NP-hard. But there could well be a canonical labeling computable in P that doesn't look anything like first lex.
As Douglas says, nauty is a graph computation package that includes a canonical labeling function. It is often very fast, but not always. Nauty uses a fancy contagious coloring algorithm. For a long time people thought that contagious coloring algorithms might in principle settle the canonical labeling and graph isomorphism problems, but eventually counterexamples were found in another classic paper by Cai, Furer, and Immerman. It was not clear at first whether this negative result would apply to nauty, but it seems that it does.