Counting simple graphs on fixed set of 4 vertices

[mikegonz00]

I started a graph theory course a few days ago, so beware, there may be some false assumptions and misuse of vocabulary below...

I understand there are 11 isomorphism classes formed by the 64 simples graphs on a fixed set of four vertices. I also understand that 64 comes from 2^6 (there are six possible edges between 2 vertices --> we make the binary decision connect/don't connect six times).

I'm just a little unsure how to calculate the size of each isomorphism class when we fix the set of four vertices. I put the picture here for reference.


I thought it might be a good idea to describe the qualities of each class and then try to count them that way, but I guess I don't really understand the qualities of each class. So far my thoughts have been...
(A) Just 1 graph (no vertex connections)
(B) (4 choose 2) graphs (pick the two adjacent vertices)
(C) Path of size 2... (4 choose 2)*(2 choose 1) graphs (pick the two adjacent vertices and then pick one of the isolated vertices)... I feel like this may be overcounting.

I assumed the complements would have the same size as well.

My question is: How does one calculate the size of each isomorphism class (A)-(K) for simple graphs fixed on 4 vertices and what is each of their sizes?

 

[Dr.Peterson]

My question is: How does one calculate the size of each isomorphism class (A)-(K) for simple graphs fixed on 4 vertices and what is each of their sizes?

You've got a lot of right ideas here, especially about complements. I'll just show my first idea for (C), without looking at yours:

One vertex is shared by the two edges, and two others are not. So choose the former (4 ways), then the latter (3 C 2 = 3 ways, or just choose which one is to be omitted), for a total of 4*3 = 12 ways.

You did the same thing, just in the opposite order. We agree! (Though I'm not sure what you meant by "two adjacent vertices".)

I found (E) and (F) easily by similar thinking, but then my total was 70 rather than 64, so I had to find which of your numbers was wrong. Think very carefully about (D); the error is subtle.

As for your ultimate question: the answer is that there are many ways to count anything, and there is no magic trick. You have to think about every combinatorical question in its own way, even each of these. But doing so definitely makes you think deeply about how each class is distinguished.

 

[mikegonz00]

You've got a lot of right ideas here, especially about complements. I'll just show my first idea for (C), without looking at yours:

One vertex is shared by the two edges, and two others are not. So choose the former (4 ways), then the latter (3 C 2 = 3 ways, or just choose which one is to be omitted), for a total of 4*3 = 12 ways.

You did the same thing, just in the opposite order. We agree! (Though I'm not sure what you meant by "two adjacent vertices".)

I found (E) and (F) easily by similar thinking, but then my total was 70 rather than 64, so I had to find which of your numbers was wrong. Think very carefully about (D); the error is subtle.

As for your ultimate question: the answer is that there are many ways to count anything, and there is no magic trick. You have to think about every combinatorical question in its own way, even each of these. But doing so definitely makes you think deeply about how each class is distinguished.

Awesome, I think I got D-F as well
(D) (Using complement) Ah this is like finding the number of necklaces with 4 distinct beads. I was overcounting by not accounting for reflections, which represent the same graph: 1/2*(4-1)!=3
(E) 4 (just pick the vertex not included in the complete subgraph K3)
(F) 12 (1. connect two vertices (4 choose 2), connect each of these to one of the two isolated vertex (2))

Thanks!