2
$\begingroup$

Are all $n$-vertex regular graphs of degree $d$ isomorphic?

Can someone provide an example of two non-isomorphic graphs $G_1$ and $G_2$ which are both regular with degree $d$ and have the same number of vertices (i.e., $|G_1| = |G_2|$)?

$\endgroup$
  • $\begingroup$ Yes indeed, but clearly regular graphs of degree 2 are not isomorphic to regular graphs of degree 3. So I'm asking about regular graphs of the same degree, if they have the same number of vertices, are they necessarily isomorphic? $\endgroup$ – Jim Newton Mar 6 at 12:37
4
$\begingroup$

Playing around with a pencil and paper for a few minutes, it should be easy to come up with non-isomorphic $d$-regular graphs with the same number of vertices, for small $d$. For example, take two cycles of length $2n$ and connect chords across them in different ways.

However, there is a polynomial-time isomorphism algorithm for any class of graphs of bounded degree, which includes the $d$-regular graphs for any fixed $d$. It's due to Luks (Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences 25(1):42–65, 1982) and uses a bunch of group theory.

$\endgroup$
4
$\begingroup$

Of course not.

Consider, for example, the cycle $C_6$ with six vertices and the graph obtained by the union of two copies of $C_3$. Then both are 2-regular, but they are obviously not isomorphic.

This is also the case if we restrict the question to connected graphs. Consider, for instance, the following two 3-regular graphs:

                                                

You can see they are not isomorphic because the second one contains cycles with six vertices that have chords; this is impossible in the first graph since it has precisely four six-cycles and you can see none of them have chords. (Or even easier: The second one has a five cycle, whereas the first one has only cycles with three, four, six, or more vertices.)

What you might be able to prove is that all 2-regular and connected graphs are isomorphic (see, e.g., this), but this is a big restriction compared to the original question.

$\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.