Find all pairwise non-isomorphic graphs

149 Views Asked by At

Task: Find all pairwise non-isomorphic graphs with $n\leq 4$ vertices.

I think that for $n = 1$ there is 1 such graph, for $n = 2$ - two, for $n = 3$ - there are 4 of them (shown in the photo), for $n = 4$ - 11 (shown in the photo). Can I combine all these sets into one, and say that there are only 18 pairwise non-isomorphic graphs with $n\leq 4$ vertices? Or, in this case, there will be graphs isomorphic to each other?

3 vertices
enter image description here

4 vertices enter image description here

1

There are 1 best solutions below

1
On BEST ANSWER

Yes, what you have is correct and so the total number will be $18$. Two graphs $G_1,G_2$ are isomorphic if there is a bijection $\phi:V(G_1)\to V(G_2)$ such that $xy\in E(G_1)\Longleftrightarrow \phi(x)\phi(y)\in E(G_2)$. In particular, since $\phi$ is a bijection, if two graphs are isomorphic they must have the same number of vertices.