Sufficient condition for graph isomorphism assuming same degree sequence

Question

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?

Answer 1

The graph with edges ab, bc, cd, de, and bf, and the graph with edges ab, bc, cd, de, and cf are both connected, have the same degree sequences, and are not isomorphic.

And here's an Eulerian example, a little bit smaller than the one given by bof. Start with an 8-cycle, a-b-c-d-e-f-g-h-a. Now whether you add the edges ac, ce, and ae, or instead add the edges ac, cf, and af, either way you get a connected graph with five vertices of degree 2 and three vertices of degree 4, hence, an Eulerian graph. But they aren't isomorphic, as you can see from the lengths of the various cycles they have.

Answer 2

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

Answer 3

As you pointed out in your question, the graphs $G=C_6$ and $H=C_3+C_3$ are a trivial example of two nonisomorphic graphs with the same degree sequence. They are the only $2$-regular graphs on $6$ vertices.

Their complements $\overline G$ and $\overline H$ are another example of two nonisomorphic graphs with the same degree sequence, and they are both connected.

$\overline G$ is the skeleton of a triangular prism, and $\overline H=K_{3,3}.$ They are (of course) the only $3$-regular graphs on $6$ vertices. They are nonisomorphic because their complements are nonisomorphic; also, only one of them is planar; also, they have different clique numbers and different chromatic numbers.

If you want an example with Eulerian graphs, consider the graphs $\overline{C_3+C_6}$ and $\overline{C_4+C_5}.$ They are nonisomorphic (because their complements are nonisomorphic), and they are
$6$-regular graphs on $9$ vertices (because their complements are $2$-regular graphs on $9$ vertices), and they are connected (because their complements are disconnected), so they are Eulerian.