Find all non-isomorphic complete bipartite graphs with at most 7 vertices?

Question

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!

Answer 1

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?).

Answer 2

Yes, it is asking you to draw or describe all the complete bipartite graphs up to $7$ vertices. The word complete is important here. Once you specify the number of vertices in each set, the graph is determined.

Answer 3

A complete bipartite graph $K_{m,n}$ is a simple graph whose vertex set is the disjoint union of two independent sets of size $m$ and $n$ with all possible edges between these sets. Hence such a graph is defined by the size of one of its independent sets. We require $m+n\leq 7$ and $m,n\ge 0$. Some people may not allow $0$ vertices in a partite set, so check your definitions.