additional condition to check if graph is complete bipartite A graph can be checked whether it is bipartite or not using a two coloring method (depth first search ) as described in Wikipedia .What are the additional conditions needed to check if graph is complete bipartite ?
https://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness
 A: To see if a graph $G$ is complete bipartite you can just use a DFS to check if $G$ is bipartite, and find a parition $A,B$ for it.
Once you have done that you just have to check if every edge between a vertex of $A$ and a vertex of $B$ is a part of $G$. (because if $G$ is complete bipartite the bipartition will be unique).
A: You can count number of edges. If number of edges in equal to number of element in first group and number of element in second group, then the bipartite graph is complete bipartite graph.
for example,
suppose nodes $V= \{a, b, c, d, e\}$ in a graph. Let the graph be bipartite with two sets $U_1 = \{a, b\}$ and $U_2 = \{c, d, e\}$
To be complete bipartite, all of the elements of U1 should be connected to each elements of $U_2$. So there must be edges
$(a,c)
(a,d)
(a,e)
(b,c)
(b,d)
(b,e)$
and no more and no less. 
So number of edges should be $2*3 = 6$ and only $6$.
A: You can also check the G and store the degrees of each node. Henceforth you can just use a DFS to check if GG is bipartite, and find a partition A,B for it.
Check if the degree of every node from 1 to n is same in partition A and B. 
