5
$\begingroup$

I'm faced with a problem in my course where I have to calculate the total number of non-isomorphic graphs. The graph is regular with an degree 4 (meaning each vertice has four edges) and has exact 7 vertices in total.

What is the correct way of handling this question?

After drawing a few graphs and messing around I came to the conclusion the graph is quite symmetric when drawn. I mean there is always one vertice you can take where you can draw a line through the graph and split in half and have two equal mirrored pieces of the graph.

If you build further on that and look I noticed you could have up to 45 or more possibilities. But I don't have a final answer and I don't know if I'm doing it right.

Any help would be appreciated. Kind Regards, Floris

  • 0
    First of all thanks for your reply. I could determine the complement, but what use do I have of it? How will it help me to calculate the total number of non-isomorphic graphs? I'm just a little confused on that part.2011-12-11

3 Answers 3

5

Let $G$ be a $4$-regular graph on $7$ vertices, and let $\overline{G}$ be the complement of $G$. $\overline{G}$ is regular; what is its degree (what you called order in your question)? What do you know about regular graphs of that degree? They’re very easy to count, and since $G_1$ is isomorphic to $G_2$ iff $\overline{G_1}$ is isomorphic to $\overline{G_2}$, counting the complements is as good as counting the graphs themselves.

(Note that the answer depends greatly on whether you’re counting labelled or unlabelled graphs. Also, I’m assuming that you’re looking only at simple graphs, i.e., without loops or multiple edges.)

Added:

To see that counting the complements is good enough, let $\mathscr{G}_n$ be the set of all simple graphs on $n$ vertices, and let $\varphi:\mathscr{G}_n\to\mathscr{G}_n:G\mapsto\overline{G}$ be the map that takes each graph in $\mathscr{G}_n$ to its complement. Then show that $\varphi$ is a bijection, and that $G\in\mathscr{G}_n$ is $k$-regular iff $\varphi(G)=\overline{G}$ is $(n-1-k)$-regular.

  • 0
    @Brian: Ok, I'm still a bit confused on the part where the # non-isomorphic graphs = # complements original graph (in my case). But you answered my question and for that you have my thanks.2011-12-12
5

The number of isomorphically distinct 2-regular graphs on 7 vertexes is the same as the number of isomorphically distinct 4-regular graphs on 7 vertexes. This is because each 2-regular graph on 7 vertexes is the unique complement of a 4-regular graph on 7 vertexes. Counting one is as good as counting the other.

The number of isomorphically distinct 2-regular simple graphs on v vertexes is equal to the number of different ways v vertexes can be represented as the sum of one or more integers greater than or equal to three (where the order of the integers in the sum is not important). This counts the number of ways one or more loops can be fit into v vertexes.

For the original question, since there are two isomorphically distinct 2-regular graphs on 7 vertexes (a single loop of all 7 vertexes, and the union of a 4-loop and a 3-loop), there are two isomorphically distinct 4-regular graphs on 7 vertexes.

1

See https://oeis.org/A051031 for the numbers of non-isomorphic regular graphs on $n$ nodes with each degree $0$ to $n-1$

  • 0
    Thanks for the website, but I really would like to know is how to get to that answer. So I can learn to do it myself next time.2011-12-11