I have just started taking graph theory at my college. Here is what I know. I understand non-isomorphic graphs and complete bipartite graphs. I am confused on this question. Is it asking for me to list all non-isomorphic complete bipartite graphs from two vertices all the way to 7 vertices? I am also lost on how I would start this. Drawing them all out? Is there an easier way to do this? My text book only gave me the definition of a bipartite graph with no examples and is now asking me to do this.
Any help would be awesome!
Best Answer
Let $A$ and $B$ be the partition sets of the graph $G$ with at most $7$ vertices. If $G$ is complete bipartite graph, for every different unordered partition set pairs $\{A,B\}$, there is only one option for $G$, up to isomorphism. So the question asks you to find in how many ways you can partition $n$ vertices into two sets $A$ and $B$, where $n \le 7$ and $|A| \ge 0$, $|B| \ge 0$ and $|A|+|B|=n$. So it is:
$0+0$
$0+1$
$0+2$
$1+1$
$0+3$
$1+2$
$0+4$
$1+3$
$2+2$
$0+5$
$1+4$
$2+3$
$0+6$
$1+5$
$2+4$
$3+3$
$0+7$
$1+6$
$2+5$
$3+4$
Therefore in total, we have $20$ different graphs satisfying given conditions, up to isomorphism (My later edit is a result of the information given here: Are the graphs with no vertex and 1 vertex bipartite?).