MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.

I have been trying to compute the value of $\sigma(n,m)$ but I have been unsuccessful. It looks hard. Is it known? Any idea or suggestion about how can $\sigma$ be computed? Or any good bounds?

share|cite|improve this question
up vote 4 down vote accepted

If $n=2m$, the answer is $2^{m-2} m! \binom{2m}{m} m^{m-2}$. Let $T_m = \sigma(n,m)$. We go through several transformations. We write $[n]$ for the set $\{ 1,2,\ldots, n \}$ and $[a,b]$ for $\{ a, a+1, \ldots, b \}$.

$T_m$ number of fully matched trees on $[2m]$.

$2 T_m$ number of fully matched trees on $[2m]$ equipped with a bipartite coloring.

$\frac{2}{\binom{2m}{m}} T_m$ number of fully matched trees where $[1,m]$ is colored white and $[m+1, 2m]$ is colored black.

$\frac{2}{m! \binom{2m}{m}} T_m$ number of fully matched trees on $[2m]$ where $i$ is matched to $m+i$.

So we need to show that the last number is $2^{m-1} m^{m-2}$. Let $U$ be one of the objects counted by the last number, and let $V$ be the tree on $[m]$ obtained by contracting the matched edges and labeling the contraction of $(i, i+m)$ by $i$. We claim that every tree $V$ on $[m]$ has $2^{m-1}$ preimages under this map. Proof: To reconstruct $U$ from $V$, for every edge $(i,j)$ of $V$, we must choose whether to join $i$ to $j+m$ or $j$ to $i+m$. This is $m-1$ independent binary choices. $\square$

I don't have any good ideas about $n>2m$, but my basic ideas would be (1) see if you can use Hall's marriage theorem to give a simple description of when a matching is maximal (2) write some code to generate a table of values, and see whether it appears in Sloane's encyclopedia of integer sequences. Looking up a table in Sloane is a bit of a black art. You should try entering several different diagonals, entering individual rows forwards and backwards, looking up any other sequences that come up in restating the problem (for example, Sloane's doesn't list $T_m$ but it does have $\frac{2}{m! \binom{2m}{m}} T_m$). I'd also factor some of the large entries in my table; if all of the prime factors of $\sigma(n,m)$ are $\leq 4n$, it seems likely there is a product formula; if not, I'd bet against it. Hmmm, this might make a good blogpost....

share|cite|improve this answer
Thanks David, consider the probability space where all the labelled trees with n vertices are equally likely. Would it be a harder question: what's the expected matching number of a random tree? Is there any paper solving that? – Patt Geffrey Jul 23 '12 at 18:35
Probably an easier one: I would expect determining the expected value to be easier than determining the whole probability distribution. I have never thought about this before, but a quick google turns up Section 6 of which seems to have relevant things to say. – David Speyer Jul 23 '12 at 19:41
One paper addressing the expected matching number is "On the Kernel of Tree Incidence Matrices" by Bauer and Golinelli ( ). Their original goal was to study the expected multiplicity of $0$ as an eigenvalue of the adjacency matrix of a random tree, but the rank of the adjacency matrix is equal to twice the size of the maximum matching (removing a leaf and its neighbor from a tree reduces the maximum matching by $1$ and the rank by $2$). – Kevin P. Costello Jul 23 '12 at 19:42

This can be done using the canonical coloring of vertices of trees into 3 colors that can be found in

Let me briefly define this coloring (using my own choice of colors). A vertex is

  • red if it belongs to all maximum independent sets
  • orange if it belongs to some max. indep. sets but not to all of them
  • green if it belongs to no max. indep. set

Then it turns out that this has something to do with maximum matchings too. In particular, the number of vertices not covered by a maximum matching is # red vertices - # green vertices.

Using a description of this coloring by local rules, one can write functional equations for the generating series of trees according to the color of their vertices.

share|cite|improve this answer
Very nice! In particular, page 5 of the second reference addresses the question of the average size of a maximal matching. – David Speyer Jan 29 '14 at 13:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.