1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ no: o-o+o-o o-o-o+o $\endgroup$ – John Dvorak Sep 28 '14 at 22:43
  • 1
    $\begingroup$ @JanDvorak What is this notation? I presume that the o is a vertex, but am in doubt about - and +. $\endgroup$ – Billy Rubina Sep 28 '14 at 22:48
  • 1
    $\begingroup$ - are edges, and + represents three vertices and four edges. Unfortunately, it's hard to draw a branching structure in ASCII $\endgroup$ – John Dvorak Sep 28 '14 at 22:58
  • 1
    $\begingroup$ another example, from chemistry: 2-methyl-pentene (isohexane) and 3-methyl-pentene (with the methyl group sitting in the middle) $\endgroup$ – John Dvorak Sep 28 '14 at 22:59
7
$\begingroup$

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

counterexample

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:

minimal counterexample

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.