Is this rule for graph isomorphism true?

Question

Is it true that two graphs are isomorphic if they:

• Have the same number of vertices;
• Have the same degree for each vertex, that is a graph with degrees $(2,3,2,3)$ would be the same as a graph with degrees $(2,2,3,3)$.
• Have no loops;
• Are connected.

I've made a few tests and this seems to be true. But I don't know how to prove it and hence am not completely sure about it.

Answer 1

It is false. The Wikipedia article on degree sequence has a counterexample with 8 vertices:

The two graphs are loopless and connected, and each has 3 vertices of degree 1, 4 vertices of degree 2, and 1 vertex of degree 3. A similar example has 6 vertices. (just delete two of the order-2 vertices in each graph.)

(An earlier post by Alexander Gruber points at this paper, “Trees with the same degree sequence and path numbers” which is relavant here.)

Addendum: The minimal counterexample has only 5 vertices and 5 edges:

Because it's so small, it can be found by hand in a few minutes by simply enumerating all graphs. This suggests that next time you have a conjecture, you might do well to try checking it for small graphs. If you haven't previously tried to draw all the small graphs, this suggests that learning to do that would be a good investment of effort.

Answer 2

No, it is not true. More generally, there is no known list of graph properties that can be checked to ensure the two given graphs are isomorphic.