# Tag Info

### Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum
Let us prove the desired bound $2(n-3)^2$ for the number of unordered odd pairs by induction on $n$, base case being $n=4$. Suppose that $n\geq 5$. Take a leaf $a$ with a unique neighbour $b$; let \$\...