2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – John Hughes Nov 27 '13 at 22:25
  • $\begingroup$ Omnomnomnom (below) says otherwise. Can you expand on your answer please? $\endgroup$ – nodebase Nov 27 '13 at 22:41
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This looks like a cool reference page but I don't quite understand how/why you think 11 is the answer. Elaborate please? $\endgroup$ – nodebase Nov 27 '13 at 22:42
  • $\begingroup$ @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? $\endgroup$ – dfeuer Nov 27 '13 at 22:50
  • $\begingroup$ Excuse my confusion yesterday. I understand the answer now. $\endgroup$ – nodebase Nov 28 '13 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.