Find all the nonisomorphic complete bipartite graphs $G=(V,E)$ where $ |V|=6$

41 Views Asked by At

I am confused by this question. The answer guide says that there are 3 graphs. i) $K_{1,5}$ ii) $K_{2,4}$ iii) $K_{3,3}$.

I don't see how I can draw them to be non isomorphic.

This question is from the textbook called Discrete and Combinatorial Mathematics, 5th Ed. Ralph Grimaldi (available online).

1

There are 1 best solutions below

0
On

This problem is asking for the number of ways one might separate the $|V|$ vertices into two groups $V_1$ and $V_2$ such that $|V_1|, |V_2|$ are not negative and $|V_1| + |V_2| = 6$. The solutions are $(|V_1|, |V_2|) = (1, 5), (2, 4),$ and $(3, 3)$. (We disregard $(5, 1), (4, 2)$ and the other $(3, 3)$ because the last solution is a duplicate and the first two violate the non-isomorphism constraint.