MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How many non-isomorphic classes of regular graphs on $(2n+1)^{m}$ vertices with $m(2n+1)^{m}$ edges with vertex degree $2m$, where $n,m \in \mathbb{N}$ are there? Is there a classification known? Can there can be more than one such class (that is are they all isomorphic)?

Is there an example of such non-isomorphic graphs if there are any?

share|cite|improve this question
Since for regular graphs, number of vertices times degree is twice the number of edges, your condition implies $m=1$? Either there is a typo or this looks like homework. – Chris Godsil Nov 29 '11 at 17:44
@Chris this is not a hw. Corrected! – user16007 Nov 29 '11 at 17:52
If you don't assume connected, then there are many non-isomorphic examples. For example, for $m=1$ and $n=3$ the 7-cycle and the disjoint union of a 4-cycle and a 3-cycle are not isomorphic. – Tony Huynh Nov 29 '11 at 18:41
up vote 7 down vote accepted

The asymptotic number of $m$-regular graphs on $N$ vertices is well understood and can be found, for example, in Bollobas' Random Graphs (the argument uses Bollobas' "configuration model"). With probability $1$ a graph has no automorphisms, so this is also the number of isomorphism classes as long as $N$ is large. In your case $N=(2n+1)^m.$ So, for a reasonably sized $n$ (since yours is a natural number, $n>0$ should be fine), if you pick two random graphs, they will be non-isomorphic.

share|cite|improve this answer
Degree at least 3 is needed. Also, you might like to divide by $N!$ to convert the asymptotic number of labelled graphs into the asymptotic number of isomorphism classes. This is ok since the number of graphs grows faster than $N!$. In my answer at I surveyed what is known about this enumeration problem. – Brendan McKay Nov 29 '11 at 23:53

For the connected case see

For example, there are two non-isomorphic connected 3-regular graphs with 6 vertices.

alt text

share|cite|improve this answer
I am interested in seeing the 5-vertex example you mention, primarily because I don't think one exists. Gerharrd "Ask Me About System Design" Paseman, 2011.11.29 – Gerhard Paseman Nov 29 '11 at 21:58
Also, the pictures you have above suggest how to build two connected 12,4 examples. Gerhard "Ask Me About System Design" Paseman, 2011.11.29 – Gerhard Paseman Nov 29 '11 at 22:01
$5=6{}{}{}{}{}$? – Gerry Myerson Nov 29 '11 at 22:07
It is the limit as $5\rightarrow 6.$ – Igor Rivin Nov 30 '11 at 4:16
Sorry for the typo. Edited it. – Robert Israel Dec 1 '11 at 5:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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