# Thread: Which complete bipartite graphs are complete?

1. ## Which complete bipartite graphs are complete?

Hello again, I come with yet another graph theory problem: which complete bipartite graphs are complete?

This implies that not all bipartite graphs are complete graphs, which I understand, as a complete graph is a graph where each pair of vertices are adjacent, and a bipartite graph can't have two connected vertices from a single set. But then, are no bipartite graph complete graphs?

A complete bipartite graph will have each vertex from a set connected by a single edge with each vertex of the second set, but this does not make it a complete graph. Will a complete bipartite graph ever be a complete graph?

2. ## Re: Which complete bipartite graphs are complete?

Originally Posted by MaryLaine
Hello again, I come with yet another graph theory problem:
which complete bipartite graphs are complete
A complete bipartite graph will have each vertex from a set connected by a single edge with each vertex of the second set, but this does not make it a complete graph. Will a complete bipartite graph ever be a complete graph?
Please read what you post. Does it make sense to you? Which black dogs are black dogs?
If the question is "When is a bipartite graph a complete graph" that can be answered.
As usual $\mathcal{K}_{m,n}$ denotes complete bipartite simple graph with $m$ vertices in one partition and the $n$.

3. ## Re: Which complete bipartite graphs are complete?

$K_{0,0}, K_{1,0}, K_{0,1}$ are all trivially complete (as the first one is the empty graph, the second and third are both graphs with a single vertex and zero edges).
$K_{1,1}$ is complete. Try $K_{1,2}$. Nope, that is one edge short of being a complete graph. Any other complete bipartite graph will not also be a complete graph. Only the four mentioned (note that $K_{1,0}$ and $K_{0,1}$ are essentially the same graph, and some professors do not want them listed separately).

4. ## Re: Which complete bipartite graphs are complete?

Originally Posted by Plato
Please read what you post. Does it make sense to you? Which black dogs are black dogs?
If the question is "When is a bipartite graph a complete graph" that can be answered.
As usual $\mathcal{K}_{m,n}$ denotes complete bipartite simple graph with $m$ vertices in one partition and the $n$.
A complete bipartite graph is not necessarily a complete graph, which I have clarified further in my post...

5. ## Re: Which complete bipartite graphs are complete?

Originally Posted by SlipEternal
$K_{0,0}, K_{1,0}, K_{0,1}$ are all trivially complete (as the first one is the empty graph, the second and third are both graphs with a single vertex and zero edges).
$K_{1,1}$ is complete. Try $K_{1,2}$. Nope, that is one edge short of being a complete graph. Any other complete bipartite graph will not also be a complete graph. Only the four mentioned (note that $K_{1,0}$ and $K_{0,1}$ are essentially the same graph, and some professors do not want them listed separately).
Yes, this makes perfect sense! Thanks a bunch!

6. ## Re: Which complete bipartite graphs are complete?

Originally Posted by SlipEternal
$K_{0,0}, K_{1,0}, K_{0,1}$ are all trivially complete (as the first one is the empty graph, the second and third are both graphs with a single vertex and zero edges).
$K_{1,1}$ is complete. Try $K_{1,2}$..
It is a gross under-statement to say that there is no standard set of definitions in graph theory.
I have never seen a definition of a graph that did not stipulate that the set of vertices is nonempty, $\mathcal{V}\ne\emptyset$.
In any case, the partition of a set never contains an empty set. Therefore, as a result of the definition of a bipartite graph $\mathcal{K}_{m,n}$ both $m\text{ and }n$ are positive integers.
This an authoritative text book. Use the "lookinside tab" go to basic concepts page. There nonempty sets for vertices are required.

If anyone knows of a text that allows an empty vertex set, please direct us to it.

7. ## Re: Which complete bipartite graphs are complete?

Originally Posted by Plato
It is a gross under-statement to say that there is no standard set of definitions in graph theory.
I have never seen a definition of a graph that did not stipulate that the set of vertices is nonempty, $\mathcal{V}\ne\emptyset$.
In any case, the partition of a set never contains an empty set. Therefore, as a result of the definition of a bipartite graph $\mathcal{K}_{m,n}$ both $m\text{ and }n$ are positive integers.
This an authoritative text book. Use the "lookinside tab" go to basic concepts page. There nonempty sets for vertices are required.

If anyone knows of a text that allows an empty vertex set, please direct us to it.
Is the null-graph a pointless concept? | SpringerLink

No conclusion is reached. I have seen texts that include it and some that dismiss it. You are probably right for bipartite graphs, so only $K_{1,1}$ is both a complete bipartite graph and a complete graph.