[Math] Sufficient condition for graph isomorphism assuming same degree sequence

combinatoricseulerian-pathgraph theorygraph-isomorphism

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:

  1. Input: Graphs $G$ and $H$.

    Output: TRUE if $G$ and $H$ are isomorphic, and FALSE otherwise.

    (This is the Graph Isomorphism Problem.)

  2. Input: Graphs $G$ and $H$ with the same degree sequence.

    Output: TRUE if $G$ and $H$ are isomorphic, and FALSE otherwise.

Formally, there is a polynomial-time reduction from the Graph Isomorphism Problem to Problem 2. above, namely:

  • Compute the degree sequences of the input graphs $G$ and $H$.
  • If the degree sequences are distinct, return FALSE.
  • Return the output of the Graph Isomorphism Problem on $G$ and $H$.

(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).

Related Question