Find the number of connected graphs with four vertices

1.7k Views Asked by At

My book has the question

Find the number of connected graphs with four vertices. (Draw them)

My understanding of connected graphs is that these are graphs were it is possible to get from every vertex in the graph to every other vertex in the graph.

The book says the answer is $5$ graphs and gives the below graphs enter image description here

But what I am trying to understand is why connected graphs like below don't count but the ones above do?

Edit: Graph c and h is isomorphic. Graph f and g is isomorphic. Isn't graph a and b isomorphic as well? And c is isomorphic with f?

enter image description here

2

There are 2 best solutions below

3
On BEST ANSWER

Your first graph above and the third graph below are the same i.e. isomorphic. The first two graphs below are also isomorphic. This had to be included in the first list however making a total of $6$.

0
On

The first and second you put are the same graph, disentangle the second. The third one is the same as the first one on the list. Now, the first one you have should be in the list and there should be $6$ graphs. http://oeis.org/A001349