New answers tagged

2 votes
Accepted

Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum

This should follow from Kirchoff's formula (and apologies in advance if I made a calculation error below). What you're asking for is the number of spanning trees that can be obtained by contracting ...
user avatar
2 votes

Counting number of special subset of vertices in a tree

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 $\...
user avatar

Top 50 recent answers are included