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|$)?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
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.