Looking into the graph isomorphism problem, after trying to use vertex degree values as anchors for determining isomorphism (Of course failing with regular graphs), the next obvious target was shortest path values.
However, when looking into using shortest path values to determine isomorphisms, it just seems too obvious. It must not work or else someone whould have discovered this already. I just can't see where this fails. I would appreciate if someone could help me see the failure condition.
With any two given graphs G and G', choose any vertex from G at random. Call this vertex Base. From here you can determine the shortest path information of all other vertices relative to the base. Vertices connected to the base have a shortest path of 1. Vertices connected to vertices connected to the base, but not the base, have a shortest path of 2, and so on. To make communication easier, consider the shortest paths as tiers. Shortest paths of 1 are tier 1, while shortest paths of 2 are tier 2 and so on.
This gives very valuable information. Each of the connections of a given vertex can only fall in one of three categories: Connected to same Tier, Connected to Tier +1, and Connected to Tier -1.
There is a non-exponental number of combinations, so it can't require exponential running time to solve. By going through both graphs and using all the vertices as bases, you get invarient graph information that can be used to create an ordered grouping that can be compared to another graph's, to determine if the two are the same.
As I said before, what am I missing? It just can't be that simple, can it?