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

  • 3
    Can you determine the complement?2011-12-11
  • 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
    I haven't seen "order" used this way. Don't you mean "degree"?2011-12-11
  • 0
    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.)2011-12-11
  • 0
    @joriki: Neither have I; I was just using Floris’s terminology without thinking.2011-12-11
  • 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.2011-12-11
  • 1
    @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?2011-12-11
  • 0
    @Floris: I’ve expanded the answer a bit; see if you can finish it now.2011-12-11
  • 1
    @Brian: So let met get this right. Two graphs are isomorphic iff their complements are isomorphic. So basicily it's the same with non-isomorphic graphs, where counting the different non-isomorphic graphs equals to counting their complements. In my example we have a graph of 7 vertices and it has a degree of 4. This graph has two complements which also means that is has two non-isomorphic graphs in total. Is this correct?2011-12-12
  • 0
    @Floris: Yes, that’s right.2011-12-12
  • 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