# How many four-vertex graphs are there up to isomorphism;

Let us call graphs $G = (V,E)$ and $G' = (V', E')$ fundamentally different if they are not isomorphic. How many fundamentally different graphs are there on four vertices?

This is a question on my homework. I'm thinking that I need to exhaust all the possible variations of a graph with four vertices:

Each vertices could have a degree of 0, 1, 2 or 3.

Four possibilities times 4 vertices = 16 possibilities.

And also, maybe, since the graphs are fundamentally different (not isomorphic), you need to minus 1 possible variation since it would match the other graph.

• There are more possibilities than that. When the degree is 2, you have several choices about which 2 nodes your node is connected to. I assume you're working with simple graphs (i.e., you cannot have an edge from a node to itself). – John Hughes Nov 27 '13 at 22:25
• Omnomnomnom (below) says otherwise. Can you expand on your answer please? – nodebase Nov 27 '13 at 22:41

As Omnomnomnom posted, there are only 11. One way to approach this solution is to break it down by the number of edges on each graph. A (simple) graph on 4 vertices can have at most ${4\choose 2}=6$ edges.

0 edges: 1 unique graph.

1 edge: 1 unique graph.

2 edges: 2 unique graphs: one where the two edges are incident and the other where they are not incident.

3 edges: 3 unique graphs. One is a 3 cycle with an isolated vertex, and the other two are trees: one has a vertex with degree 3 and the other has 2 vertices with degree 2.

4 edges: 2 unique graphs: a 4 cycle and one containing a 3 cycle.

5 edges: 1 unique graph.

6 edges: 1 unique graph.

There are $11$ fundamentally different graphs on $4$ vertices.

• This looks like a cool reference page but I don't quite understand how/why you think 11 is the answer. Elaborate please? – nodebase Nov 27 '13 at 22:42
• @DiscreteGenius, Omnomnomnom counted the eleven four-vertex graphs listed on that page and came up with the number eleven. Are you asking how that list was constructed, or how to count to eleven? – dfeuer Nov 27 '13 at 22:50
• Excuse my confusion yesterday. I understand the answer now. – nodebase Nov 28 '13 at 16:38