Prove number of spanning trees in $K_{a,b}$ 
The hint given for this question is "use the inclusion-exclusion principle", but honestly, I have no idea where to start with this question...
 A: Here we are interested in determining $T(r,s)$, the number of spanning trees in $K_{r,s}$.  One way we could try to count them is to identify which vertices are the leaves of the tree.  Given subsets $A$ of the $r$ vertices in the first part, and $B$ of the $s$ vertices in the second part, how many trees have $A \cup B$ as the set of leaves?
It is reasonably simple to ensure that the vertices in $A \cup B$ should be leaves: after removing the leaves, we are left with a tree on what remains, and so there are $T(r - |A|, s - |B|)$ ways to form the tree on the remaining vertices.  For each leaf, we must then attach it to some vertex from this remaining part of the tree.  Since the tree lives in $K_{r,s}$, the leaves in $A$ must attach to the $s - |B|$ vertices from the second part, while the leaves in $B$ attach to the $r - |A|$ vertices in the first part.  Hence there are $(s - |B|)^{|A|} (r - |A|)^{|B|}$ ways to attach these leaves, giving a total of $T(r - |A|, s - |B|) (s - |B|)^{|A|} (r - |A|)^{|B|}$ trees where the vertices in $A \cup B$ are leaves.
This looks very similar to what we have in part (a).  The problem is that we cannot guarantee that the vertices in $A \cup B$ are the only leaves in these trees: the subtree counted in $T(r - |A|, s - |B|)$ will also have some leaves, and if none of them got chosen by the leaves in $A \cup B$, those leaves will still be leaves in the final tree.  To correct for this overcounting, we have to use the Inclusion-Exclusion formula.  Doing so should give the expression in (a).  Note that the $i = j = 0$ term is precisely $T(r,s)$, so this equation implicitly gives a value for $T(r,s)$ in terms of its value for smaller parameters.
In part (b), we are asked to give an explicit formula for $T(r,s)$; namely to show that $T(r,s) = r^{s-1} s^{r-1}$.  While there may be a shortcut to this final answer, this problem is screaming out for induction - plug the formula into the equality from (a) and try to solve for $T(r,s)$.  The sum should split into a product of two sums (one over $i$ and one over $j$), which will simplify its evaluation.
A: Shagnik has treated (a) pretty thoroughly. I’ll offer two approaches to (b). The first is based on (a). Define $f(r,s)=r^{s-1}s^{r-1}$; I claim that $f$ satisfies the recurrence given in (a) for $T$, i.e.,
$$\sum_{i,j}\binom{r}i\binom{s}j(-1)^{i+j}f(r-i,s-j)(s-j)^i(r-i)^j=0\;.$$
In other words,
$$\sum_{i,j}\binom{r}i\binom{s}j(-1)^{i+j}(r-i)^{s-1}(s-j)^{r-1}=0\;.$$
To prove this, note that it can be rewritten as a product of summations:
$$\begin{align*}
&\sum_{i,j}\binom{r}i\binom{s}j(-1)^{i+j}(r-i)^{s-1}(s-j)^{r-1}\\
&\qquad=\sum_i\left((-1)^i\binom{r}i(r-i)^{s-1}\sum_j(-1)^j\binom{s}j(s-j)^{r-1}\right)\\
&\qquad=\left(\sum_i(-1)^i\binom{r}i(r-i)^{s-1}\right)\left(\sum_j(-1)^j\binom{s}j(s-j)^{r-1}\right)\;.\tag{1}
\end{align*}$$
Then recognize
$$\sum_i(-1)^i\binom{r}i(r-i)^{s-1}$$
as the number of surjections from $[s-1]$ onto $[r]$, either by an inclusion-exclusion argument or by realizing that it is equal to
$$r!{{s-1}\brace r}\;,$$
where ${{s-1}\brace r}$ is a Stirling number of the second kind equal to the number of partitions of $[s-1]$ into $r$ non-empty parts. Use this to see that at least one of the factors in $(1)$ is always $0$.
Finally, show that $f$ satisfies the same initial conditions as $T$ and must therefore be the same function.

It is also possible to adapt Pitman’s proof of Cayley’s formula for the number of labelled trees on $n$ vertices to give a combinatorial proof that $T(r,s)=r^{s-1}s^{r-1}$; I’m including it partly because I like combinatorial arguments and partly so that I can find it again.
Let $A$ and $B$ be the parts of the bipartition of $K_{r,s}$, with $|A|=r$ and $|B|=s$. We will count in two ways the ordered triples of a rooted, directed spanning tree for $K_{r,s}$, a permutation of its edges from $A$ to $B$, and a permutation of its edges from $B$ to $A$.
There are $T(r,s)$ ways to choose a spanning tree. We then choose a root for $T$; this establishes an orientation for each of the edges (away from the root). If we choose the root in $A$, there are $r$ ways to do so, $s$ edges from $A$ to $B$, and $r-1$ edges from $B$ to $A$, so there are 
$$r(r-1)!s!T(r,s)=r!s!T(r,s)$$
such ordered triples. If we choose the root in $B$ there are $s$ ways to do so, $r$ edges from $B$ to $A$, and $s-1$ edges from $A$ to $B$, so there are again $r!s!T(r,s)$ such triples, for a grand total of
$$2r!s!T(r,s)$$
triples.
Alternatively, we can build a rooted, directed spanning tree by picking a root and then adding edges one at a time. We start with a forest of $r+s$ trees, each consisting of a root and nothing else. Each time we add an edge, its target will be an existing root, which will then cease to be a root, and the number of trees in the forest will decrease by $1$. When we’ve added $r+s-1$ edges, we’ll have a single rooted, directed spanning tree, and the order in which we’ve added the edges will provide the permutations that are the second and third components of the ordered triple.
We first pick a root. Suppose that we pick it in $A$; there are $r$ ways to do so. This root can never be the target of a directed edge of the tree, but each root in $B$ must eventually be the target of an edge, as must each root in $A$ other than the designated root. 
We first add edges to the roots in $B$. When we add the first edge, there are $r$ choices of origin and $s$ of target. When we add the second edge, there are still $r$ choices of origin, but there are only $s-1$ choices of target, since the previous target is no long a root in the forest. In general there are $r$ choices of origin and $s+1-k$ choices of target when we add the $k$-th edge from $A$ to $B$, so the total number of sequences in which these edges can be added is $r^ss!$. Similarly, there are $s^{r-1}(r-1)!$ sequences in which we can add the $r-1$ edges from $B$ to $A$, for a total of 
$$r^ss!\cdot s^{r-1}(r-1)!=r^{s-1}s^{r-1}r!s!$$
ordered triples whose spanning trees have their roots in $A$. By symmetry there are 
$$s^rr!\cdot r^{s-1}(s-1)!=r^{s-1}s^{r-1}r!s!$$
ordered triples whose spanning trees have their roots in $B$, for a grand total of
$$2r!s!r^{s-1}s^{r-1}$$
ordered triples. Thus, 
$$2r!s!r^{s-1}s^{r-1}=2r!s!T(r,s)\;,$$
and therefore 
$$T(r,s)=r^{s-1}s^{r-1}\;.$$
