0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The second one is isomorphic to the first one below. $\endgroup$ – Vladislav Apr 12 at 14:39
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Isn't the first one and the second one above also isomorphic? $\endgroup$ – Sam Apr 12 at 14:47
  • 1
    $\begingroup$ The first and second in the list of $5$ graphs from the textbook are not isomorphic. The second has a vertex of degree $3$, whereas the first does not. $\endgroup$ – kccu Apr 12 at 14:51
  • 1
    $\begingroup$ If you mean first and second graphs in the first figure, then no, they are not isomorphic. One has a vertex of degree $3$ and another does not. $\endgroup$ – PJK Apr 12 at 14:52
1
$\begingroup$

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

$\endgroup$

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.