Max possible height corresponds to the spanning tree generated by the BFS of the complete bipartite graph Km,n ..
Say we have {v1 , v2 , v3 ......., vm} in one partition of vertices and { t1 , t2 , ....... , tn } in the other vertex set..
So DFS can be done as selecting vertex from one of the sets alternately..So say we start DFS from v1 , then we reach to t1 from v1 , then to v2 from t1 , then to t2 from v2 and so on..
This way we will have max height = number of edges [ because in each step we are traversing to a descendent not sibling ]
= m + n - 1 [ As number of vertices = m + n ]
Hence max height possible as far as DFS tree is concerned = m + n - 1..
For BFS, we can take one vertex in v1.. Now after that we push all its neighbors in the queue which are in the vertex set 2..All of them will be pushed as it is a complete bipartite graph.. Hence max height in this case = 1.