Here's the question from my homework: (1) "Let a and b be positive integers. Define a graph as follows: $K_a$,$_b$ = (V, E), where V can be partitioned into two disjoint sets of size a and b. That is, V=A $\cup$ B, where |A| = a, |B| = b, and A $\cap$ B = $\emptyset$. The edge set is
E = { { u , v } : (u $\in$ A $\land$ v $\in$ B }
That is, the graph contains every edge from an element of A to an element of B, but no edges between two elements of A or two elements of B.
The first question (a) says: "Prove: $K_a$,$_b$ is connected.
The second question (b) says: Find and prove a necessary and sufficient condition on a and b for $K_a$,$_b$ to be a tree.
For the first question, all I know so far to say is: "In order for $K_a$,$_b$ to be connected, there must be only one component and at least one edge." Any help or suggestions on where to go from here would be appreciated.
As for the second question I think I've found an answer, but in case it's related to the answer for part a I figured I'd include it in writing this up.
For part (a), $K_{a,b}$ is connected if there exists a path between any two vertices $u$ and $v$ of $K_{a,b}$. Clearly if $u$ belongs to $A$ and $v$ belongs to $B$, they are connected by the edge $uv$. So consider $u$ and $v$ in the same component. Can you find a path between them?
For part (b), $K_{a,b}$ is a tree if it is connected and has no cycles. We've shown that it's connected. Under what conditions will no cycle exist in $K_{a,b}$?