0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I think wikipedia gives enough examples for an understanding. For a beginning, ask yourself in how many ways you can write 7 as the sum of two natural numbers. $\endgroup$ – M. Winter Jan 17 '18 at 23:12
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Not everyone will agree that the "graph" with no vertices (the so-called null graph not to be confused with an empty graph) is even a graph; in fact, I believe it's a minority opinion to admit the null graph. $\endgroup$ – bof Jan 18 '18 at 0:53
  • $\begingroup$ I believe in my class for a bipartite graph to be complete every vertex in X is joined to every vertex of Y. So wouldn't every input with 0 be incomplete? $\endgroup$ – BuiZMath Jan 18 '18 at 5:16
  • $\begingroup$ Actually my answer before editing wasn't including $0$ vertex sets (I wasn't agreeing either), I changed it after reading the question I added to my answer. If that's what you concluded in your class, then you can just remove the cases with $0$ vertex to get $12$ as the answer. As long as you get the idea of finding them, rest is about what is expected from you in your class (in graph theory, there are many examples like this one where there are more than one opinion/definition of something). $\endgroup$ – ArsenBerk Jan 18 '18 at 9:21
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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