Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Can you determine the complement? –  Chris Godsil Dec 11 '11 at 17:20
    
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. –  Floris Devriendt Dec 11 '11 at 17:48
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
I haven't seen "order" used this way. Don't you mean "degree"? –  joriki Dec 11 '11 at 19:15
    
Yeah I may have used the wrong word for this. With order or degree of 4 I meant that each vertice has 4 edges. About using the complement, I still dont know how I will calculate it. I know the complement of a graph with 7 vertices and a degree of 4 is a graph with a degree of two. What does this help me? (Lets say we work with unlabeled graphs, in my question I worked labeled graphs but I realise this should not be the case.) –  Floris Devriendt Dec 11 '11 at 19:43
    
@joriki: Neither have I; I was just using Floris’s terminology without thinking. –  Brian M. Scott Dec 11 '11 at 20:10
1  
@Floris: There’s only one connected $2$-regular graph on $7$ vertices; what is it? If you can answer that question, you should also be able to see what can happen if $\overline{G}$ is not connected. –  Brian M. Scott Dec 11 '11 at 20:12
    
@Brian: So far I have this: A graph with 7 vertices and a degree of 4 has two complementary graphs, one connected as you pointed out (a 7 vertices cycle with a degree of 2), and one non-connected graph (a cycle with 3 vertices and a cycle of 4 vertices, both having a degree of 2). I still don't understand why this is the amount of non-isomorphic graphs for the given graph. Could you maybe explain it a little bit further? –  Floris Devriendt Dec 11 '11 at 21:57
show 4 more comments

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.

share|improve this answer
add comment

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

share|improve this answer
    
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. –  Floris Devriendt Dec 11 '11 at 22:01
add comment

Your Answer

 
discard

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.