We assume graph to be simple undirected.
In general, having the same degree sequence is not sufficient for two graphs to be isomorphic. A trivial example is a hexagon which is connected and two separated triangles, which is obviously not connected, yet their degree sequences are the same.
Can we also exhibit counter examples with two non-isomorphic connected graphs having the same degree sequence? What about two such Euler graphs?
Is it known for which extra conditions having the same degree sequence becomes sufficient for isomorphism?
Best Answer
There is no meaningful distinction between the two decision problems:
Input: Graphs $G$ and $H$.
Output:
TRUE
if $G$ and $H$ are isomorphic, andFALSE
otherwise.(This is the Graph Isomorphism Problem.)
Input: Graphs $G$ and $H$ with the same degree sequence.
Output:
TRUE
if $G$ and $H$ are isomorphic, andFALSE
otherwise.Formally, there is a polynomial-time reduction from the Graph Isomorphism Problem to Problem 2. above, namely:
FALSE
.(I leave off the tedious details of verifying it's actually a polynomial-time reduction.)
There is no known polynomial time algorithm for solving the Graph Isomorphism Problem. So while there are sufficient conditions for checking if $G$ and $H$ are isomorphic (e.g., compute canonical labels via Nauty), they're not going to be mathematically succinct (although they may be useful in practice).