The Average Size of Matchings in Graphs

Abstract

In this paper, we consider the average size of independent edge sets, also called matchings, in a graph. We characterize the extremal graphs for the average size of matchings in general graphs and trees. In addition, we obtain inequalities between the average size of matchings and the number of matchings as well as the matching energy, which is defined as the sum of the absolute values of the zeros of the matching polynomial.

1 Introduction

An independent vertex set in a graph is a set of vertices such that no two vertices are adjacent. An independent edge set, also called a matching, is a set of edges such that no two edges are adjacent. It is not surprising that these two concepts are closely related, an elementary example being the fact that a matching in a graph is an independent set in the corresponding line graph. Two popular graph invariants associated with these concepts are the Merrifield–Simmons index and the Hosoya index, which are the total number of independent sets and the total number of matchings respectively. Extremal problems, where one is looking for the maximum or minimum of an invariant in a specified class of graphs, have been studied quite thoroughly for both the Merrifield–Simmons index and the Hosoya index. It is straightforward that among all n-vertex graphs, the complete graph has the maximum Hosoya index and the minimum Merrifield–Simmons index, while on the other hand the empty graph has the minimum Hosoya index and the maximum Merrifield–Simmons index. Among n-vertex trees, the path and the star are extremal, and there are numerous other examples of graph classes where the graphs that minimize the Merrifield–Simmons index also maximize the Hosoya index, and vice versa [13].

In a recent paper [1], we were interested in extremal questions for the average size of independent sets of graphs rather than their number. This was partly inspired by the work of Jamison [6, 7] and later authors [5, 10, 12, 14] on the average size of subtrees of trees. In the present paper, which complements our paper [1], we are concerned with the study of the average size of matchings in a graph. In view of the aforementioned relation between independent sets and matchings, we expect to get similar results as for the average size of independent sets. Indeed, we find that the graphs that minimize the average size of independent sets are also those that maximize the average size of matchings and vice versa in all instances that we treat. Specifically, it holds true for arbitrary graphs and trees of a prescribed size.

Finally, we also prove inequalities between the average size of matchings and the number of matchings as well as the matching energy of a graph, an invariant introduced in [4].

2 Preliminaries

Let G be a graph. A subset A of E(G) is called a matching of G if no pair of edges of A share a common vertex. Let ${\text {m}}(G,k)$ be the number of matchings of cardinality k (also called k-matchings) in G. We use the following notation for the total number of matchings in G, the sum of the sizes of all matchings in G and the average size of matchings in G:

$$\begin{aligned} {\text {M}}(G)&= \sum _{k\ge 0}{\text {m}}(G,k),\\ {\text {S}}(G)&= \sum _{k\ge 0}k\,{\text {m}}(G,k),\\ {\text {avm}}(G)&= \frac{{\text {S}}(G)}{{\text {M}}(G)}. \end{aligned}$$

The greatest cardinality of a matching in G is called the matching number of G and denoted by $\mu (G)$.

As examples, let us consider the n-vertex edgeless graph $E_n$ and the star $S_n$. We have

$$\begin{aligned} {\text {M}}(E_n)=1,\quad {\text {M}}(S_n)=n, \quad {\text {S}}(E_n)=0,\quad {\text {S}}(S_n)=n-1 \end{aligned}$$

and hence

$$\begin{aligned} {\text {avm}}(E_n)=0, \quad {\text {avm}}(S_n)=\frac{n-1}{n}. \end{aligned}$$

The following standard and well-known proposition gives us a recursion for the total number and size of matchings.

Proposition 1

If$e=uv$is an edge ofG, then

$$\begin{aligned} {\text {M}}(G)={\text {M}}(G-e)+{\text {M}}(G-v-u) \end{aligned}$$

(1)

and

$$\begin{aligned} {\text {S}}(G)={\text {S}}(G-e)+ {\text {S}}(G-v-u)+ {\text {M}}(G-v-u). \end{aligned}$$

(2)

Similarly, ifvis a vertex ofG, then

$$\begin{aligned} {\text {M}}(G)={\text {M}}(G-v)+\sum _{u: uv \in E(G)}{\text {M}}(G-v-u) \end{aligned}$$

(3)

and

$$\begin{aligned} {\text {S}}(G)={\text {S}}(G-v)+\sum _{u: uv \in E(G)}({\text {S}}(G-v-u)+{\text {M}}(G-v-u)). \end{aligned}$$

(4)

Proof

A matching in G either contains the edge e or not. The number of matchings containing e is ${\text {M}}(G-v-u)$, and the number of those not containing e is ${\text {M}}(G-e)$. Hence, the first equation holds. The argument for the second equation is similar, with the last term taking the edge e itself into account.

Using similar reasoning, the last two equations are obtained by distinguishing between matchings that do not contain an edge with v as an endpoint and those that do contain such an edge. $\square$

Remark 1

In particular, if v is a leaf of a tree and w its unique neighbor, we obtain the relations

$$\begin{aligned} {\text {M}}(G)={\text {M}}(G-v)+{\text {M}}(G-v-w) \end{aligned}$$

and

$$\begin{aligned} {\text {S}}(G) = {\text {S}}(G-v) + {\text {S}}(G-v-w) + {\text {M}}(G-v-w). \end{aligned}$$

Moreover, we have the following basic result on disjoint unions:

Proposition 2

Let$G_1,G_2,\ldots ,G_k$be the connected components of a graphG. Then we have

$$\begin{aligned} {\text {M}}(G) = \prod _{j=1}^k {\text {M}}(G_j) \end{aligned}$$

and

$$\begin{aligned} {\text {S}}(G) = \sum _{i=1}^k {\text {S}}(G_i) \prod _{\begin{array}{c} j=1 \\ j \ne i \end{array}}^k {\text {M}}(G_j) = {\text {M}}(G) \sum _{i=1}^k \frac{{\text {S}}(G_i)}{{\text {M}}(G_i)}, \end{aligned}$$

thus

$$\begin{aligned} {\text {avm}}(G) = \sum _{i=1}^k {\text {avm}}(G_i). \end{aligned}$$

Proof

This follows easily from the fact that every matching of G decomposes uniquely into matchings of its connected components. $\square$

3 General Graphs

Unlike the total number of matchings ${\text {M}}$, the average size of matchings ${\text {avm}}$ is not always a monotone function under addition of edges to the graph. For example, consider the tree in Fig. 1. We have

Fig. 1

A tree T and two of its edges

$$\begin{aligned} {\text {avm}}(T-e_1)=\frac{7}{6}>\frac{8}{7}={\text {avm}}(T), \text { but } {\text {avm}}(T-e_2)=\frac{3}{4}<\frac{8}{7}={\text {avm}}(T). \end{aligned}$$

However, we can make use of the following result obtained in [1]:

Theorem 1

LetXbe a nonempty finite set, and${\mathcal {P}}(X)$its powerset. For a set${\mathcal {A}}\subseteq {\mathcal {P}}(X)$, we define

$$\begin{aligned} av({\mathcal {A}})=\frac{1}{|{\mathcal {A}}|}\sum _{A\in {\mathcal {A}}}|A|. \end{aligned}$$

Let${\mathcal {B}}\subseteq {\mathcal {P}}(X)$, such that the cardinalities of the elements of${\mathcal {B}}$are not all the same and for every$x\in X$there exists$B\in {\mathcal {B}}$with$x\in B$. Then there exists$x_0\in X$such that

$$\begin{aligned} av({\mathcal {B}})>av\left( {\mathcal {B}}\cap {\mathcal {P}}(X-\{x_0\})\right) . \end{aligned}$$

Applying Theorem 1, with ${\mathcal {B}}$ being the set of matchings of G, we immediately obtain the following theorem.

Theorem 2

IfGis a nonempty graph, then there exists an edgeeinE(G) such that

$$\begin{aligned} {\text {avm}}(G-e)<{\text {avm}}(G). \end{aligned}$$

As an immediate consequence, we have the following corollary (which of course is also rather trivial without Theorem 2).

Corollary 1

For everyn-vertex graphGthat is not the edgeless graph$E_n$, $0={\text {avm}}(E_n) < {\text {avm}}(G)$.

One might wonder whether there is an analogous statement for adding edges. If it was possible to add an edge to every non-complete graph in such a way that the average matching size increases, it would follow immediately that complete graphs maximize the invariant ${\text {avm}}$. While the latter is true (as will be shown in the following), the analogue of Theorem 1 fails, as the example of a four-vertex cycle shows: when an edge e is added to the cycle $C_4$, we have

$$\begin{aligned} {\text {avm}}(C_4) = \frac{8}{7} > \frac{9}{8} = {\text {avm}}(C_4 + e). \end{aligned}$$

Thus we need another approach to show that the complete graph is still extremal. For this purpose, we first introduce some notation.

In analogy to ${\text {M}}(G)$, ${\text {S}}(G)$ and ${\text {avm}}(G)$, we define the following partial quantities for every nonnegative integer k:

$$\begin{aligned} {\text {M}}_k(G)&=\sum _{i=0}^k{\text {m}}(G,i),\\ {\text {S}}_k(G)&=\sum _{i=0}^ki \,{\text {m}}(G,i),\\ {\text {avm}}_k(G)&=\frac{S_k(G)}{{\text {M}}_k(G)}. \end{aligned}$$

We have the following lemmas.

Lemma 1

For every nonnegative integerkand every graphG, we have

$$\begin{aligned} {\text {avm}}_{k+1}(G)\ge {\text {avm}}_k(G). \end{aligned}$$

If$k\ge \mu (G)$, then

$$\begin{aligned} {\text {avm}}_{k+1}(G)= {\text {avm}}_k(G)={\text {avm}}(G). \end{aligned}$$

Proof

This is straightforward from the definition of ${\text {avm}}_k$. $\square$

Lemma 2

For everyn-vertex graphGand every nonnegative integerksuch that$k < \mu (G)$, we have

$$\begin{aligned} \frac{{\text {m}}(K_n,k)}{{\text {m}}(K_n,k+1)}\le \frac{{\text {m}}(G,k)}{{\text {m}}(G,k+1)}. \end{aligned}$$

Proof

Let N be any k-matching of the complete graph $K_n$. When the 2k vertices that are covered by N are removed, a complete graph on $n-2k$ vertices remains. Thus there are ${\text {m}}(K_{n-2k},1) = \left( {\begin{array}{c}n-2k\\ 2\end{array}}\right)$ possible ways to extend N to a $(k+1)$-matching. Conversely, every $(k+1)$-matching can be obtained as an extension of $k+1$ different k-matchings. It follows that

$$\begin{aligned} {\text {m}}(K_n,k+1) = {\text {m}}(K_n,k) \cdot \frac{{\text {m}}(K_{n-2k},1)}{k+1}. \end{aligned}$$

(5)

Likewise, if N is a k-matching of G and v(N) the set of vertices covered by N in G, then there are ${\text {m}}(G - v(N))$ ways to extend N to a $(k+1)$-matching of G. So by the same double-counting argument, we have

$$\begin{aligned} {\text {m}}(G,k+1) = \frac{1}{k+1} \sum _{N:\,k\text {-matching of } G} {\text {m}}(G - v(N),1). \end{aligned}$$

Clearly, ${\text {m}}(G - v(N),1) \le {\text {m}}(K_{n-2k},1)$ for all k-matchings N (with equality if and only if $G - v(N)$ is complete), thus

$$\begin{aligned} {\text {m}}(G,k+1) \le \frac{1}{k+1} \cdot {\text {m}}(G,k) \cdot {\text {m}}(K_{n-2k},1), \end{aligned}$$

(6)

and the desired inequality results from (5) and (6). $\square$

Remark 2

Equality in Lemma 2 may hold for some (but not all) k even if G is not complete: for example, for the 4-cycle $C_4$, we have

$$\begin{aligned} \frac{{\text {m}}(K_4,2)}{{\text {m}}(K_4,1)} = \frac{3}{6} = \frac{2}{4} = \frac{{\text {m}}(C_4,2)}{{\text {m}}(C_4,1)}. \end{aligned}$$

Lemma 2 can easily be extended to the following lemma by induction:

Lemma 3

For everyn-vertex graphGand for every pair of integersk, lwith$\mu (G)\ge k \ge l \ge 0$, we have

$$\begin{aligned} \frac{{\text {m}}(K_n,l)}{{\text {m}}(K_n,k)}\le \frac{{\text {m}}(G,l)}{{\text {m}}(G,k)} \end{aligned}$$

and thus

$$\begin{aligned} \frac{{\text {M}}_{l}(K_n)}{{\text {m}}(K_n,k)} = \frac{\sum _{i=0}^l{\text {m}}(K_n,i)}{{\text {m}}(K_n,k)}\le \frac{\sum _{i=0}^l{\text {m}}(G,i)}{{\text {m}}(G,k)} = \frac{{\text {M}}_{l}(G)}{{\text {m}}(G,k)}. \end{aligned}$$

Theorem 3

For everyn-vertex graphGand every integerkwith$\mu (G)\ge k > 0$, we have

$$\begin{aligned} {\text {avm}}_k(K_n)\ge {\text {avm}}_k(G), \end{aligned}$$

with equality if and only ifGis a complete graph.

Proof

We only need to consider the case that G is not complete.

We proceed by induction on k. For $k=1$ we have

$$\begin{aligned} {\text {avm}}_1(K_n)=\frac{|E(K_n)|}{|E(K_n)|+1} > \frac{|E(G)|}{|E(G)|+1}={\text {avm}}_1(G). \end{aligned}$$

The inequality holds because $\frac{x}{x+1}$ is an increasing function of x on the interval $[0,\infty )$.

Assume that ${\text {avm}}_k(K_n) > {\text {avm}}_k(G)$ for some positive integer k, where $k <\mu (G)$. Then we have ${\text {m}}(k+1,G)\ne 0$ and

$$\begin{aligned} {\text {avm}}_{k+1}(K_n)&=\frac{(k+1){\text {m}}(K_n,k+1)+\sum _{i=0}^ki\,{\text {m}}(K_n,i)}{{\text {m}}(K_n,k+1) +\sum _{i=0}^k{\text {m}}(K_n,i)}\nonumber \\&=\frac{(k+1){\text {m}}(K_n,k+1)+{\text {S}}_k(K_n)}{{\text {m}}(K_n,k+1)+{\text {M}}_k(K_n)}\nonumber \\&=\frac{(k+1){\text {m}}(K_n,k+1)+{\text {avm}}_k(K_n){\text {M}}_k(K_n)}{{\text {m}}(K_n,k+1) +{\text {M}}_k(K_n)}\nonumber \\&=\frac{(k+1)+{\text {avm}}_k(K_n)\frac{{\text {M}}_k(K_n)}{{\text {m}}(K_n,k+1)}}{1+\frac{{\text {M}}_k(K_n)}{{\text {m}}(K_n,k+1)}}. \end{aligned}$$

(7)

Since $k+1>{\text {avm}}_k(K_n)$, we know that $\frac{(k+1) + {\text {avm}}_k(K_n)x}{1+x}$ is decreasing as a function of x on the interval $[0,\infty )$, so Lemma 3 and (7) imply that

$$\begin{aligned} {\text {avm}}_{k+1}(K_n)&\ge \frac{(k+1)+{\text {avm}}_k(K_n)\frac{{\text {M}}_k(G)}{{\text {m}}(G,k+1)}}{1+\frac{{\text {M}}_k(G)}{{\text {m}}(G,k+1)}}. \end{aligned}$$

(8)

Finally, using the induction hypothesis ${\text {avm}}_k(K_n) > {\text {avm}}_k(G)$, we obtain

$$\begin{aligned} {\text {avm}}_{k+1}(K_n)&> \frac{(k+1)+{\text {avm}}_k(G)\frac{{\text {M}}_k(G)}{{\text {m}}(G,k+1)}}{1+\frac{{\text {M}}_k(G)}{{\text {m}}(G,k+1)}}={\text {avm}}_{k+1}(G). \end{aligned}$$

(9)

$\square$

Corollary 2

For everyn-vertex graphGwe have${\text {avm}}(K_n)\ge {\text {avm}}(G)$, with equality only ifGis a complete graph.

Proof

Theorem 3 and Lemma 1 give us

$$\begin{aligned} {\text {avm}}(K_n)={\text {avm}}_{\lfloor n/2\rfloor }(K_n)\ge {\text {avm}}_{\mu (G)}(K_n)\ge {\text {avm}}_{\mu (G)}(G)={\text {avm}}(G). \end{aligned}$$

$\square$

Remark 3

While there is no simple explicit formula for ${\text {avm}}(K_n)$, it can be expressed in terms of the number of matchings in complete graphs. Every edge of the complete graph $K_n$ is contained in ${\text {M}}(K_{n-2})$ matchings, thus we have ${\text {S}}(K_n) = \left( {\begin{array}{c}n\\ 2\end{array}}\right) {\text {M}}(K_{n-2})$ and consequently

$$\begin{aligned} {\text {avm}}(K_n) = \frac{{\text {S}}(K_n)}{{\text {M}}(K_n)} = \left( {\begin{array}{c}n\\ 2\end{array}}\right) \frac{{\text {M}}(K_{n-2})}{{\text {M}}(K_n)}. \end{aligned}$$

A relatively simple asymptotic formula can be provided as well. There is a straightforward bijection between matchings of $K_n$ and involutions of an n-element set (a permutation is called an involution if it is equal to its own inverse, or equivalently if all cycles are of length 1 or 2). Thus the number of matchings of $K_n$ is the same as the number of involutions of an n-element set, for which there is a well-known asymptotic formula (see [3, Proposition VIII.2]):

$$\begin{aligned} {\text {M}}(K_n) \sim \frac{1}{\sqrt{2}} n^{n/2} e^{-n/2+\sqrt{n}-1/4}. \end{aligned}$$

It follows that

$$\begin{aligned} {\text {avm}}(K_n) \sim \frac{n}{2} \end{aligned}$$

as $n \rightarrow \infty$.

4 Trees

In this section, we will be concerned with trees. Our main goal is to determine the maximum and minimum of ${\text {avm}}(T)$ when T is a tree with n vertices. Let us first consider the problem of minimizing the average size of matchings. As it turns out, the minimum for trees is also the minimum for connected graphs in general.

Theorem 4

For every connectedn-vertex graph, ${\text {avm}}(S_n) \le {\text {avm}}(G)$, with equality only ifGis a star.

Proof

We have shown earlier that ${\text {avm}}(S_n)=\frac{n-1}{n}<1$. However any other connected graph G (except for the complete graph $K_3$, for which ${\text {avm}}(K_3)=\frac{3}{4} > \frac{2}{3}$) on n vertices satisfies ${\text {avm}}(G)\ge 1$, since it possesses matchings of size greater than 1, which make up for the empty set. $\square$

The maximization problem requires more effort. Note that the line graph of the n-vertex path $P_n$ is the $(n-1)$-vertex path $P_{n-1}$. This implies that the matchings of $P_{n}$ can be identified with the independent sets of $P_{n-1}$. Thus, the average size of matchings of $P_{n}$ is the same as the average size of the independent sets of $P_{n-1}$. A formula for this average size was determined in [1], where it was also shown that this average is in fact the minimum among trees of the same size.

Lemma 4

The average size of matchings of then-vertex path$P_n$is

$$\begin{aligned} {\text {avm}}(P_n)= \frac{5 - \sqrt{5}}{10} n + \frac{1-\sqrt{5}}{10} - \frac{n+1}{\sqrt{5}((-\phi ^2)^{n+1}-1)}, \end{aligned}$$

(10)

where$\phi = \frac{\sqrt{5}+1}{2}$is the golden ratio. In particular,

• (a) $\lim \nolimits _{n \rightarrow \infty } {\text {avm}}(P_n) - \frac{5 - \sqrt{5}}{10} n = \frac{1-\sqrt{5}}{10},$

• (b) $\displaystyle {\text {avm}}(P_n) \le \frac{5-\sqrt{5}}{10} n + \frac{1}{\sqrt{5}} - \frac{1}{2}$, with equality only for$n = 2$. For all positive integers$n \ne 2$, we even have$\displaystyle {\text {avm}}(P_n) \le \frac{5-\sqrt{5}}{10} n + \frac{2}{\sqrt{5}} - 1$.

Proof

The formula for ${\text {avm}}(P_n)$ is taken from [1] (using the aforementioned correspondence between matchings of $P_n$ and independent sets of $P_{n-1}$). The limit in (a) is a straightforward consequence. For (b), one only needs to note that the sign of the final term in (10) alternates, and that its absolute value is decreasing in n (see also [1]). It follows that its maximum is attained for $n=2$, and the second largest value for $n=4$. $\square$

For ease of notation, we set $a= \frac{5-\sqrt{5}}{10} \approx 0.27639320$ and $c_n = {\text {avm}}(P_n) - an$. As mentioned above, the final in (10) has alternating sign, and its absolute value is decreasing. Thus we have

$$\begin{aligned} c_1< c_3< c_5< \cdots< c_6< c_4 < c_2. \end{aligned}$$

(11)

Table 1 gives values of $c_n$ for small n.

Table 1 Values of $c_1,c_2,\ldots ,c_5$

Before we prove the main result of this section, we require one more lemma:

Lemma 5

For every graphGand every vertexvofG, we have

$$\begin{aligned} \frac{1}{1+ d(v)}\le \frac{{\text {M}}(G-v)}{{\text {M}}(G)} \le 1, \end{aligned}$$

whered(v) denotes the degree ofv.

Proof

Note first that ${\text {M}}(G) = {\text {M}}(G-v) + \sum _{u:uv \in E(G)} {\text {M}}(G-v-u)$. Since $G-v-u$ is a subgraph of $G-v$, we have ${\text {M}}(G-v-u) \le {\text {M}}(G-v)$, hence ${\text {M}}(G) \le (1+d(v)){\text {M}}(G-v)$, which proves the first inequality. The second inequality simply follows from the fact that $G-v$ is a subgraph of G, so matchings of $G- v$ are also matchings of G. $\square$

Theorem 5

For every treeTof ordernthat is not a path, we have the inequality${\text {avm}}(T) \le an + b$, where$b = (7\sqrt{5}-17)/10 \approx -0.13475241$. Consequently, the path maximizes the value of${\text {avm}}(T)$among all trees of ordern.

Proof

We prove the inequality by induction on n. For $n \le 3$, there is nothing to prove since the only trees with three or fewer vertices are paths. Thus assume now that $n \ge 4$, and consider a vertex v of the tree T whose degree is at least 3 (which must exist if T is not a path). Denote the neighbors of v by $v_1,v_2,\ldots ,v_k$ and the components of $T - v$ by $T_1,T_2,\ldots ,T_k$ (in such a way that $v_j$ is contained in $T_j$). Let e be the edge between v and $v_k$, and $T' = T - T_k$ be the tree obtained by removing $T_k$ from T. We have

$$\begin{aligned} {\text {avm}}(T)&= \frac{{\text {S}}(T)}{{\text {M}}(T)} = \frac{{\text {S}}(T-e) + {\text {S}}(T-v-v_k)+{\text {M}}(T-v-v_k)}{{\text {M}}(T)} \nonumber \\&= \frac{{\text {M}}(T-e)}{{\text {M}}(T)} \cdot \frac{{\text {S}}(T-e)}{{\text {M}}(T-e)} + \frac{{\text {M}}(T-v-v_k)}{{\text {M}}(T)} \cdot \left( 1 + \frac{{\text {S}}(T-v-v_k)}{{\text {M}}(T-v-v_k)}\right) \nonumber \\&=\frac{{\text {M}}(T-e)}{{\text {M}}(T)} {\text {avm}}(T-e) + \frac{{\text {M}}(T) - {\text {M}}(T-e)}{{\text {M}}(T)} (1+ {\text {avm}}(T-v-v_k))\nonumber \\&=\frac{{\text {M}}(T-e)}{{\text {M}}(T)} ({\text {avm}}(T')+{\text {avm}}(T_k)) \nonumber \\&\quad + \left( 1 - \frac{{\text {M}}(T-e)}{{\text {M}}(T)} \right) \left( 1 + \sum _{j=1}^{k-1} {\text {avm}}(T_j) + {\text {avm}}(T_k-v_k)\right) . \end{aligned}$$

(12)

Set $A={\text {avm}}(T')+{\text {avm}}(T_k)$ and $B=1 + \sum _{j=1}^{k-1} {\text {avm}}(T_j) + {\text {avm}}(T_k-v_k)$.

Assume first that $k \ge 4$. By Lemma 4 and the induction hypothesis, we have ${\text {avm}}(T_j) \le a|T_j| + \frac{1}{\sqrt{5}} - \frac{1}{2}$ for all j and ${\text {avm}}(T')\le a|T'|+b$. It follows that

$$\begin{aligned} A \le a(|T'|+|T_k|)+b+ \frac{1}{\sqrt{5}} - \frac{1}{2} = a |T| + b + \frac{1}{\sqrt{5}} - \frac{1}{2} < a|T|+b. \end{aligned}$$

If $B \le a|T|+b$, then we are done immediately. Hence we can assume that $A < a|T|+b \le B$. This implies that the expression for ${\text {avm}}(T)$ in (12) is decreasing regarded as a function of $\frac{{\text {M}}(T-e)}{{\text {M}}(T)}$, which means that we will need lower bounds for this quotient. So let us first find a formula for $\frac{{\text {M}}(T-e)}{{\text {M}}(T)}$. We observe that

$$\begin{aligned} \frac{{\text {M}}(T-e)}{{\text {M}}(T)}=\frac{{\text {M}}(T'){\text {M}}(T_k)}{{\text {M}}(T'){\text {M}}(T_k) +{\text {M}}(T'-v){\text {M}}(T_k-v_k)}, \end{aligned}$$

thus

$$\begin{aligned} \frac{{\text {M}}(T-e)}{{\text {M}}(T)}=\left( 1+\frac{{\text {M}}(T'-v)}{{\text {M}}(T')}\cdot \frac{{\text {M}}(T_k-v_k)}{{\text {M}}(T_k)} \right) ^{-1}. \end{aligned}$$

(13)

Let us also find an expression for $\frac{{\text {M}}(T'-v)}{{\text {M}}(T')}$:

$$\begin{aligned} \frac{{\text {M}}(T'-v)}{{\text {M}}(T')}&=\frac{\prod _{j=1}^{k-1}{\text {M}}(T_j)}{\prod _{j=1}^{k-1}{\text {M}}(T_j)+\sum _{j=1}^{k-1} {\text {M}}(T_j-v_j) \prod _{\begin{array}{c} i=1 \\ i \ne j \end{array}}^{k-1} {\text {M}}(T_i) }\nonumber \\&= \left( 1+\sum _{j=1}^{k-1}\frac{{\text {M}}(T_j-v_j)}{{\text {M}}(T_j)}\right) ^{-1}. \end{aligned}$$

(14)

Moreover, by Lemma 5, we have $\frac{{\text {M}}(T'-v)}{{\text {M}}(T')} \le 1$, and plugging this estimate into (13), we obtain

$$\begin{aligned} \frac{{\text {M}}(T-e)}{{\text {M}}(T)}\ge \left( 1+\frac{{\text {M}}(T_k-v_k)}{{\text {M}}(T_k)} \right) ^{-1}. \end{aligned}$$

(15)

We have to consider two different cases:

Case 1: One of the $T_j$’s is the two-vertex path $P_2$. Then we can without loss of generality assume that $T_k=P_2$, so that ${\text {avm}}(T_k) = \frac{1}{2}$ and ${\text {avm}}(T_k - v_k) = 0$. Let us distinguish two subcases depending on the number of other branches $T_j$ that are isomorphic to $P_2$.

• At least one of the $T_j$’s is different from $P_2$. We have

  $$\begin{aligned} A \le a|T|+b+\frac{1}{\sqrt{5}} - \frac{1}{2}, \end{aligned}$$

  as it was established earlier. Moreover, by Lemma 4 and the induction hypothesis,

  $$\begin{aligned} {\text {avm}}(T_j) \le a|T_j| + \frac{1}{\sqrt{5}} - \frac{1}{2} \end{aligned}$$

  for all j, and

  $$\begin{aligned} {\text {avm}}(T_j) \le a|T_j| + \frac{2}{\sqrt{5}} - 1 \end{aligned}$$

  if $T_j$ is different from $P_2$. Since this is the case for at least one index j, it follows that

  $$\begin{aligned} B&= 1 + \sum _{j=1}^{k-1} {\text {avm}}(T_j) \\&\le 1+ \sum _{j=1}^{k-1} a|T_j| + (k-2) \left( \frac{1}{\sqrt{5}}-\frac{1}{2}\right) +\frac{2}{\sqrt{5}}-1\\&= a (|T| - 3) + (k-2) \left( \frac{1}{\sqrt{5}}-\frac{1}{2}\right) +\frac{2}{\sqrt{5}} \\&\le a(|T|-3) + 2 \left( \frac{1}{\sqrt{5}}-\frac{1}{2}\right) +\frac{2}{\sqrt{5}}\\&= a|T|-3a+\frac{4}{\sqrt{5}}-1. \end{aligned}$$

  Since we are assuming that $T_k$ is a two-vertex path, we have $\frac{{\text {M}}(T_k-v_k)}{{\text {M}}(T_k)}= \frac{1}{2}$. Plugging this into (15), we obtain $\frac{{\text {M}}(T-e)}{{\text {M}}(T)} \ge \frac{2}{3}$. Hence, (12) gives us

  $$\begin{aligned} {\text {avm}}(T)&\le a|T| + \frac{2}{3}\left( b+\frac{1}{\sqrt{5}} - \frac{1}{2}\right) +\frac{1}{3}\left( -3a+\frac{4}{\sqrt{5}}-1\right) \\&= a|T|+\frac{29}{6\sqrt{5}}-\frac{23}{10}\approx a|T|-0.13847 < a|T|+b. \end{aligned}$$

• All of the $T_j$’s are equal to $P_2$. In this case, we can determine ${\text {M}}(T)$ and ${\text {S}}(T)$ explicitly (as functions of k only) by means of Proposition 1:

  $$\begin{aligned} {\text {M}}(T) = 2^k + k2^{k-1} \end{aligned}$$

  and

  $$\begin{aligned} {\text {S}}(T) = k2^{k-1} + k(k+1)2^{k-2}, \end{aligned}$$

  thus

  $$\begin{aligned} {\text {avm}}(T) = \frac{k^2+3k}{2k+4}. \end{aligned}$$

  Now one verifies easily that

  $$\begin{aligned} {\text {avm}}(T) = \frac{k^2+3k}{2k+4} \le a(2k+1)+b = a|T| + b \end{aligned}$$

  holds for all $k \ge 4$, completing the proof in Case 1.

Case 2: None of the $T_j$’s is a 2-vertex path $P_2$.

Let us distinguish different cases depending on the shape of $T_k$. We may assume that $T_k$ is the smallest branch, i.e. $|T_k|=\min _{1\le j\le k}|T_j|$.

• If $|T_k|=1$, then ${\text {avm}}(T_k)={\text {avm}}(T_k-v_k)=0$. It follows that

  $$\begin{aligned} A = {\text {avm}}(T') \le a|T'|+b=a|T|+b-a. \end{aligned}$$

  Moreover, since ${\text {avm}}(T_j) \le |T_j| + \frac{2}{\sqrt{5}} - 1$ for every j by the induction hypothesis and Lemma 4 (and the assumption that none of the $T_j$ is a 2-vertex path), we have

  $$\begin{aligned} B&= 1 + \sum _{j=1}^{k-1} {\text {avm}}(T_j) \\&\le 1 + a \sum _{j=1}^{k-1} |T_j| + (k-1) \left( \frac{2}{\sqrt{5}}-1\right) \\&\le 1 + a (|T|-2) + 3 \left( \frac{2}{\sqrt{5}}-1\right) \\&= a|T|-2a+\frac{6}{\sqrt{5}}-2. \end{aligned}$$

  Since $\frac{{\text {M}}(T_k-v_k)}{{\text {M}}(T_k)}=1$, (15) gives us $\frac{{\text {M}}(T-e)}{{\text {M}}(T)} \ge \frac{1}{2}$. Thus,

  $$\begin{aligned} {\text {avm}}(T)&\le \frac{1}{2}\left( a|T|+b-a\right) +\frac{1}{2}\left( a|T|-2a +\frac{6}{\sqrt{5}}-2\right) \\&= a|T|+\frac{11}{2\sqrt{5}}-\frac{13}{5}\approx a|T| -0.14033 < a|T|+b. \end{aligned}$$

• If $|T_k|=3$, then ${\text {avm}}(T_k)=a|T_k|+\frac{3}{2\sqrt{5}}-\frac{5}{6}$ and ${\text {avm}}(T_k-v_k)\le a(|T_k|-1)+\frac{1}{\sqrt{5}}-\frac{1}{2}$. In the same way as in the previous case, it follows that

  $$\begin{aligned} A&\le a|T|+b+\frac{3}{2\sqrt{5}}-\frac{5}{6},\\ B&\le 1+a(|T|-2)+3\left( \frac{2}{\sqrt{5}}-1\right) + \frac{1}{\sqrt{5}}-\frac{1}{2}= a|T|-2a+\frac{7}{\sqrt{5}}-\frac{5}{2}. \end{aligned}$$

  Since $\frac{{\text {M}}(T_k-v_k)}{{\text {M}}(T_k)} \le \frac{2}{3}$, in this case (15) gives us $\frac{{\text {M}}(T-e)}{{\text {M}}(T)} \ge \frac{3}{5}$. We obtain

  $$\begin{aligned} {\text {avm}}(T)&\le a|T|+\frac{3}{5}\left( b+\frac{3}{2\sqrt{5}}-\frac{5}{6}\right) +\frac{2}{5}\left( -2a+\frac{7}{\sqrt{5}}-\frac{5}{2}\right) \\&= a|T|+\frac{31}{5\sqrt{5}}-\frac{73}{25}\approx a|T|-0.14728 < a|T|+b. \end{aligned}$$

• If $|T_k|=4$, then ${\text {avm}}(T_k)\le a|T_k|+\frac{2}{\sqrt{5}}-1$ and ${\text {avm}}(T_k-v_k)\le a(|T_k|-1)+\frac{3}{2\sqrt{5}}-\frac{5}{6}$. In the same way as before, it follows that

  $$\begin{aligned} A&\le a|T|+b+\frac{2}{\sqrt{5}}-1,\\ B&\le 1+a(|T|-2)+3\left( \frac{2}{\sqrt{5}}-1\right) +\frac{3}{2\sqrt{5}}-\frac{5}{6}= a|T|-2a+\frac{3\sqrt{5}}{2}-\frac{17}{6}. \end{aligned}$$

  Moreover, $\frac{{\text {M}}(T_k-v_k)}{{\text {M}}(T_k)} \le \frac{3}{4}$ in this case, so using (15) again, we get $\frac{{\text {M}}(T-e)}{{\text {M}}(T)} \ge \frac{4}{7}$. Hence

  $$\begin{aligned} {\text {avm}}(T)&\le a|T|+\frac{4}{7}\left( b+\frac{2}{\sqrt{5}}-1\right) +\frac{3}{7}\left( -2a+\frac{3\sqrt{5}}{2}-\frac{17}{6}\right) \\&= a|T|+\frac{19\sqrt{5}}{14}-\frac{223}{70}\approx a|T|-0.15105 < a|T|+b. \end{aligned}$$

• If $|T_k|\ge 5$, then ${\text {avm}}(T_j)\le a|T_j|+\frac{3}{\sqrt{5}}-\frac{19}{13}$ for all j (by the induction hypothesis and (11), we have ${\text {avm}}(T_j) \le a|T_j| + c_6 = a|T_j| + \frac{3}{\sqrt{5}}-\frac{19}{13}$ if $T_j$ is a path, and ${\text {avm}}(T_j) \le a|T_j| + b \le a|T_j| + \frac{3}{\sqrt{5}}-\frac{19}{13}$ otherwise) and ${\text {avm}}(T_k-v_k)\le a(|T_k|-1)+\frac{2}{\sqrt{5}}-1$. So it follows now that

  $$\begin{aligned} A&\le a|T|+b+\frac{3}{\sqrt{5}}-\frac{19}{13},\\ B&\le 1+a(|T|-2)+3\left( \frac{3}{\sqrt{5}}-\frac{19}{13}\right) +\frac{2}{\sqrt{5}}-1 = a|T|-2a+ \frac{11}{\sqrt{5}}-\frac{57}{13}. \end{aligned}$$

  Since $\frac{{\text {M}}(T_k-v_k)}{{\text {M}}(T_k)}\le 1$, we have $\frac{{\text {M}}(T-e)}{{\text {M}}(T)} \ge \frac{1}{2}$ by (15). Thus,

  $$\begin{aligned} {\text {avm}}(T)&\le a|T| +\frac{1}{2} \left( b+\frac{3}{\sqrt{5}}-\frac{19}{13} -2a+ \frac{11}{\sqrt{5}}-\frac{57}{13} \right) \\&= a|T|+\frac{37}{4\sqrt{5}}-\frac{1111}{260}\approx a|T|-0.13635 < a|T|+b. \end{aligned}$$

This completes the proof in the case that $k \ge 4$, so we are left with the case $k=3$. We return to the representation

$$\begin{aligned} {\text {avm}}(T)&= \frac{{\text {M}}(T-e)}{{\text {M}}(T)} ({\text {avm}}(T')+{\text {avm}}(T_k)) \\&\quad + \left( 1-\frac{{\text {M}}(T-e)}{{\text {M}}(T)}\right) \left( 1 + \sum _{j=1}^{k-1} {\text {avm}}(T_j) +{\text {avm}}(T_k-v_k)\right) \nonumber . \end{aligned}$$

(16)

Plugging (14) into (13), we obtain

$$\begin{aligned} \frac{{\text {M}}(T-e)}{{\text {M}}(T)}=\left( 1+\frac{1}{1+\sum _{j=1}^{k-1} \frac{{\text {M}}(T_j-v_j)}{{\text {M}}(T_j)}}\cdot \frac{{\text {M}}(T_k-v_k)}{{\text {M}}(T_k)} \right) ^{-1}. \end{aligned}$$

(17)

Now we distinguish different cases depending on how many of the branches $T_j$ have one, two, three, four and five or more vertices respectively. This gives us a total of 35 cases corresponding to the solutions of

$$\begin{aligned} x_1+x_2+x_3+x_4+x_5 = 3. \end{aligned}$$

Here, $x_1,x_2,x_3,x_4$ stand for the number of $T_j$’s with one, two, three, and four vertices respectively, and $x_5$ is the number of $T_j$’s with five or more vertices. In each of the cases, we use the following explicit values and bounds. The bounds and explicit values for $|T_j| \le 4$ are obtained by an exhaustive case check, while the bounds for $|T_j| > 4$ follow from the induction hypothesis and Lemma 4.

$$\begin{aligned}&{\text {avm}}(T_j) {\left\{ \begin{array}{ll} = a|T_j|-a &{}|T_j| = 1, \\ = a|T_j|+c_2 &{}|T_j| = 2, \\ = a|T_j|+c_3 &{}|T_j| = 3, \\ \le a|T_j|+c_4&{}|T_j|=4,\\ \le a|T_j| + c_6 &{} \text {otherwise,} \end{array}\right. }\\&{\text {avm}}(T_j-v_j) {\left\{ \begin{array}{ll} = a|T_j|-a &{}|T_j| = 1, \\ = a|T_j|-2a &{}|T_j| = 2, \\ \le a(|T_j|-1)+c_2 &{}|T_j| = 3,\\ \le a(|T_j|-1)+c_3 &{}|T_j| = 4,\\ \le a(|T_j|-1)+c_4 &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

We can assume that the degree of $v_j$ is at most 3 for every j, since otherwise we can go back to the case that $k \ge 4$. Using this assumption, we have

$$\begin{aligned} \frac{{\text {M}}(T_j-v_j)}{{\text {M}}(T_j)} {\left\{ \begin{array}{ll} = 1 &{}|T_j| = 1, \\ = \frac{1}{2} &{}|T_j| = 2, \\ \in \left[ \frac{1}{3},\frac{2}{3}\right] &{}|T_j| = 3, \\ \in \left[ \frac{2}{5}, \frac{3}{4}\right] &{}|T_j| = 4, \\ \in \left[ \frac{4}{11},\frac{3}{4}\right] &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

The first four statements are obtained by checking all possible cases. For the last one, we use a similar recursion to (14) combined with Lemma 5 as follows: note first that $v_j$ has at most two neighbors in $T_j$, since its degree in T is at most 3. If there is only one neighbor, let w be this neighbor, and set $S = T_j - v_j$. We have

$$\begin{aligned} \frac{{\text {M}}(T_j-v_j)}{{\text {M}}(T_j)} = \left( 1 + \frac{{\text {M}}(S-w)}{{\text {M}}(S)} \right) ^{-1}. \end{aligned}$$

Applying Lemma 5 to S and w yields $\frac{1}{3} \le \frac{{\text {M}}(S-w)}{{\text {M}}(S)} \le 1$ (if the degree of w was greater than 2, we could go back to the case $k \ge 4$ again), thus $\frac{{\text {M}}(T_j-v_j)}{{\text {M}}(T_j)} \in [\frac{1}{2},\frac{3}{4}]$. If there are two neighbors $w_1$ and $w_2$, let $S_1$ and $S_2$ be the respective components of $T_j - v_j$. Since $\frac{1}{3} \le \frac{{\text {M}}(S_i-w_i)}{{\text {M}}(S_i)} \le 1$, we obtain

$$\begin{aligned} \frac{{\text {M}}(T_j-v_j)}{{\text {M}}(T_j)} = \left( 1 + \frac{{\text {M}}(S_1-w_1)}{{\text {M}}(S_1)}+\frac{{\text {M}}(S_2-w_2)}{{\text {M}}(S_2)}\right) ^{-1} \le \frac{1}{1+\frac{1}{3} + \frac{1}{3}} = \frac{3}{5} \end{aligned}$$

in this case, which readily proves the upper bound of $\frac{3}{4}$ in all cases. To improve the lower bound even further, we can note that one of the two trees $S_1$ and $S_2$ has more than one vertex; without loss of generality, let this be $S_1$. Applying the same argument to $S_1$ as to $T_j$, we find $\frac{{\text {M}}(S_1-w_1)}{{\text {M}}(S_1)} \le \frac{3}{4}$. Thus

$$\begin{aligned} \frac{{\text {M}}(T_j-v_j)}{{\text {M}}(T_j)} = \left( 1 + \frac{{\text {M}}(S_1-w_1)}{{\text {M}}(S_1)}+\frac{{\text {M}}(S_2-w_2)}{{\text {M}}(S_2)} \right) ^{-1} \ge \frac{1}{1+\frac{3}{4} + 1} = \frac{4}{11}, \end{aligned}$$

and we have also established the lower bound.

Next we return to the representation (16). Note that $|T'|\ge 3$, so the induction hypothesis combined with (11) yields

$$\begin{aligned} {\text {avm}}(T') \le {\text {avm}}(P_{|T'|}) = a |T'| + c_{|T'|} \le a|T'| + c_4. \end{aligned}$$

The same reasoning shows that ${\text {avm}}(T_k) \le a|T_k| + c_2$, thus ${\text {avm}}(T')+{\text {avm}}(T_k)\le (a|T'|+c_4)+(a|T_k|+c_2)<a|T|+b$. As before, if $1+\sum _{j=1}^{k-1}{\text {avm}}(T_j) + {\text {avm}}(T_j-v_j)\le a|T|+b$, then we are done. So we may assume that

$$\begin{aligned} {\text {avm}}(T')+{\text {avm}}(T_k)<a|T|+b\le 1+\sum _{j=1}^{k-1}{\text {avm}}(T_j)+ {\text {avm}}(T_j-v_j). \end{aligned}$$

Hence the expression (16) is linear and decreasing in $\frac{{\text {M}}(T-e)}{{\text {M}}(T)}$, and thus its maximum is attained for the smallest possible value of $\frac{{\text {M}}(T-e)}{{\text {M}}(T)}$.

By the induction hypothesis, ${\text {avm}}(T')\le {\text {avm}}(P_{|T'|}) = a|T'| + c_{|T'|}$. This inequality is plugged into (16) along with the bounds for ${\text {avm}}(T_j)$ and ${\text {avm}}(T_j-v_j)$. The identity (17) is used to obtain a lower bound on the quotient $\frac{{\text {M}}(T-e)}{{\text {M}}(T)}$. All this gives us an upper bound for ${\text {avm}}(T)$ in each of the aforementioned 35 cases, which can all be checked easily with a computer. The worst case happens when $x_1=x_3=x_4=x_5=0$ and $x_2=3$, where we have the equality ${\text {avm}}(T)=a|T|+b$. As another example to illustrate the general procedure, let us consider the case that gives us the second worst estimate: it is obtained for $x_1=x_3=x_5=0$, $x_2=2$ and $x_4=1$. Let $T_2$ and $T_3$ both have two vertices, so that the first branch $T_1$ consists of four vertices. Note that $T_3$ is isomorphic to $P_2$ and ${\text {avm}}(T_1) \le {\text {avm}}(P_4)$ from the first part of the proof. We then have

$$\begin{aligned} {\text {avm}}(T_3) = a|T_3|+ c_2,\ {\text {avm}}(T') \le a|T'|+c_7, \end{aligned}$$

thus

$$\begin{aligned} {\text {avm}}(T') + {\text {avm}}(T_3) \le a|T| + c_2 + c_7 = a|T| + \frac{9}{2\sqrt{5}} - \frac{46}{21}. \end{aligned}$$

Moreover,

$$\begin{aligned} {\text {avm}}(T_3-v_3) = 0,\ {\text {avm}}(T_1) \le 4a + c_4,\ {\text {avm}}(T_2) = \frac{1}{2}, \end{aligned}$$

and thus

$$\begin{aligned} 1 + \sum _{j=1}^2 {\text {avm}}(T_j) + {\text {avm}}(T_3-v_3) \le 1 + 4a+c_4 + \frac{1}{2} = a|T| + \frac{9}{2\sqrt{5}} - 2. \end{aligned}$$

Finally, we have

$$\begin{aligned} \frac{{\text {M}}(T-e)}{{\text {M}}(T)}&= \left( 1 + \frac{{\text {M}}(T_3-v_3)}{{\text {M}}(T_3)} \cdot \frac{1}{1+\frac{{\text {M}}(T_1-v_1)}{{\text {M}}(T_1)} +\frac{{\text {M}}(T_2-v_2)}{{\text {M}}(T_2)}}\right) ^{-1}\\&\ge \left( 1+\frac{1}{2} \cdot \frac{1}{1+\frac{1}{2} + \frac{2}{5}}\right) ^{-1} = \frac{19}{24}. \end{aligned}$$

Putting everything together, we obtain

$$\begin{aligned} {\text {avm}}(T)&= \frac{{\text {M}}(T-e)}{{\text {M}}(T)} \left( {\text {avm}}(T') + {\text {avm}}(T_3) \right) \\&\quad + \left( 1-\frac{{\text {M}}(T-e)}{{\text {M}}(T)}\right) \left( 1 + \sum _{j=1}^2 {\text {avm}}(T_j) + {\text {avm}}(T_3-v_3)\right) \\&\le \frac{{\text {M}}(T-e)}{{\text {M}}(T)} \left( a|T| + \frac{9}{2\sqrt{5}} - \frac{46}{21} \right) \\&\quad + \left( 1-\frac{{\text {M}}(T-e)}{{\text {M}}(T)}\right) \left( a|T| + \frac{9}{2\sqrt{5}} - 2 \right) \\&\le \frac{19}{24} \left( a|T| + \frac{9}{2\sqrt{5}} - \frac{46}{21} \right) + \frac{5}{24} \left( a|T| + \frac{9}{2\sqrt{5}} - 2 \right) \\&= a|T| + \frac{9}{2\sqrt{5}}-\frac{271}{126}\approx a|T| -0.13833 <a|T|+b. \end{aligned}$$

The other cases are treated in the same fashion and give upper bounds with smaller constant terms. Thus the induction is complete. In order to complete the proof of the theorem, we only need a lower bound on ${\text {avm}}(P_n)$. However, (11) shows that

$$\begin{aligned} {\text {avm}}(P_n) = an + c_n \ge an + c_5 \end{aligned}$$

for $n > 3$, and $c_5 = \frac{\sqrt{5}}{2} - \frac{5}{4} \approx -0.131966 > b$. Thus ${\text {avm}}(P_n) > an + b \ge {\text {avm}}(T)$ for every tree T with n vertices other than $P_n$. This completes the proof. $\square$

5 Relations to Other Invariants

In this section, we will prove inequalities between the average matching size and other matching-related quantities associated with a graph. Let G be an n-vertex graph. The matching polynomial and the matching generating polynomial are defined as follows:

$$\begin{aligned}&\varPhi (G,x)=\sum _{k\ge 0}{\text {m}}(G,k)(-1)^k x^{n-2k},\\&{\text {M}}(G,x)=\sum _{k\ge 0}{\text {m}}(G,k)x^k. \end{aligned}$$

Note that the average size of matchings in G can be expressed as

$$\begin{aligned} {\text {avm}}(G)=\frac{\sum _{k\ge 0}k\,{\text {m}}(G,k)}{\sum _{k\ge 0}{\text {m}}(G,k)}=\frac{{\text {M}}'(G,1)}{{\text {M}}(G,1)}, \end{aligned}$$

where ${\text {M}}'(G,x)$ is the first derivative of ${\text {M}}(G,x)$ with respect to x.

It is easy to see that $\varPhi (G,x) = x^n {\text {M}}(G,-\frac{1}{x^2})$. Using this relation, we can write the derivative of $\varPhi$ in terms of M and its derivative as follows:

$$\begin{aligned} \varPhi '(G,x)=nx^{n-1}{\text {M}}\left( G,-\frac{1}{x^2}\right) +2x^{n-3}{\text {M}}'\left( G,-\frac{1}{x^2}\right) . \end{aligned}$$

This gives us

$$\begin{aligned} \frac{\varPhi '(G,x)}{\varPhi (G,x)}=\frac{n}{x}+\frac{2}{x^3} \frac{{\text {M}}'\left( G,-\frac{1}{x^2}\right) }{{\text {M}}\left( G,-\frac{1}{x^2}\right) }. \end{aligned}$$

(18)

Let $\mu _1,\mu _2,\dots ,\mu _n$ be the zeros of the matching polynomial $\varPhi (G,x)$; it is well-known that these zeros are real, see for example Section 8.5 in [9]. Now we can express $\varPhi$ and $\varPhi '$ in terms of the zeros as follows:

$$\begin{aligned} \varPhi (G,x)&=\prod _{j=1}^n(x-\mu _j),\\ \varPhi '(G,x)&=\sum _{k=1}^n \frac{\prod _{j=1}^n(x-\mu _j)}{x-\mu _k}. \end{aligned}$$

Therefore,

$$\begin{aligned} \frac{\varPhi '(G,x)}{\varPhi (G,x)}=\sum _{k=1}^n\frac{1}{x-\mu _k}. \end{aligned}$$

(19)

Now, we can establish a relation between the average size of matchings of G and the zeros of its matching polynomial.

Lemma 6

LetGbe ann-vertex graph and$\mu _1,\dots ,\mu _n$be the zeros of the matching polynomial ofG. Then

$$\begin{aligned} {\text {avm}}(G)=\frac{1}{2}\sum _{j=1}^n\frac{\mu _j^2}{\mu _j^2+1}. \end{aligned}$$

Proof

Using (18) and (19), and plugging in $x=i$, we obtain

$$\begin{aligned} \sum _{j=1}^n\frac{1}{i-\mu _j} = \frac{n}{i}+\frac{2}{i^3}\frac{{\text {M}}'\left( G,1\right) }{{\text {M}}\left( G,1\right) }, \end{aligned}$$

and this simplifies to

$$\begin{aligned} \sum _{j=1}^n\frac{\mu _j}{\mu _j-i} = 2\,{\text {avm}}(G). \end{aligned}$$

(20)

Let us rearrange the left hand side of (20). We have

$$\begin{aligned} \sum _{j=1}^n\frac{\mu _j}{\mu _j-i}=\sum _{j=1}^n\frac{\mu _j(\mu _j +i)}{(\mu _j-i)(\mu _j+i)}=\sum _{j=1}^n\frac{\mu _j^2+i\mu _j}{\mu _j^2+1}. \end{aligned}$$

Since the imaginary part must be 0, we get the desired result. $\square$

Having established this relation, we can now prove two inequalities. The first relates the average matching size with the total number of matchings. Note that the latter is ${\text {M}}(G) = {\text {M}}(G,1)$, which can be expressed in terms of the zeros $\mu _1,\dots ,\mu _n$ as well:

$$\begin{aligned} {\text {M}}(G) = {\text {M}}(G,1) = |{\text {M}}(G,1)| = |i^{-n} \varPhi (G,i)| = \left| \prod _{j=1}^n (i-\mu _j) \right| = \prod _{j=1}^n \sqrt{1+\mu _j^2}. \end{aligned}$$

It is not difficult to verify that the inequality

$$\begin{aligned} \frac{x}{1+x} \le \beta \log (1+x) + 1 - \beta + \beta \log \beta \end{aligned}$$

holds for all positive real numbers $\beta$ and x. Plugging in $\mu _j^2$ for x and summing over all j yields the following result:

Proposition 3

For every positive real number$\beta$and everyn-vertex graphG, we have

$$\begin{aligned} {\text {avm}}(G) \le \beta \log {\text {M}}(G) + \left( 1-\beta +\beta \log \beta \right) \frac{n}{2}. \end{aligned}$$

In particular,

$$\begin{aligned} {\text {avm}}(G) \le \log {\text {M}}(G). \end{aligned}$$

We can still choose $\beta$ arbitrarily. Differentiating with respect to $\beta$, we find that the optimal value for $\beta$ (that minimizes the upper bound) is $\beta = {\text {M}}(G)^{-2/n}$. Plugging this back into the inequality, we obtain the following theorem:

Theorem 6

For everyn-vertex graph, we have

$$\begin{aligned} {\text {avm}}(G) \le \frac{n}{2} \left( 1 - {\text {M}}(G)^{-2/n} \right) . \end{aligned}$$

An alternative way to prove this theorem is to apply the inequality between the arithmetic and the geometric mean.

We conclude this section with a similar inequality involving the matching energy. This invariant is defined as follows [4]:

$$\begin{aligned} {\text {ME}}(G)=\sum _{j=1}^n|\mu _j|. \end{aligned}$$

Following an analogous approach, we can prove a relation between the average size of matchings in G and the matching energy of G.

Theorem 7

For every graphG,

$$\begin{aligned} {\text {ME}}(G)\ge 4\,{\text {avm}}(G). \end{aligned}$$

Proof

For all nonnegative real x, we have $\frac{x^2}{1+x^2} \le \frac{x}{2}$. Therefore, by Lemma 6,

$$\begin{aligned} {\text {avm}}(G) = \frac{1}{2} \sum _{j=1}^n \frac{\mu _j^2}{1+\mu _j^2} \le \frac{1}{2} \sum _{j=1}^n \frac{|\mu _j|}{2} = \frac{1}{4} {\text {ME}}(G). \end{aligned}$$

$\square$

Remark 4

Note that in the case of trees, the matching polynomial coincides with the characteristic polynomial. So we have a correspondence between the average size of matchings of a tree and the classical energy of a tree, which is the sum of the absolute values of the eigenvalues, see [8].

6 The Weighted Average Size of Matchings in a Graph

In the context of the monomer-dimer model from statistical physics, one often considers a probability distribution on the set of matchings where the probability of a k-matching is proportional to $\alpha ^k$ for some constant $\alpha$, see for example [2]. This provides the motivation to study the weighted average size of matchings. We consider a random matching according to the aforementioned probability distribution, where $\alpha$ is a fixed positive number. We define the weighted total number of matchings in G, the weighted total size of G and the weighted average size of matchings in G as follows:

$$\begin{aligned} {\text {M}}^{\alpha }(G)&=\sum _{k\ge 0}{\text {m}}(G,k)\alpha ^k,\\ {\text {S}}^{\alpha }(G)&=\sum _{k\ge 0}k\,{\text {m}}(G,k)\alpha ^k,\\ {\text {avm}}^{\alpha }(G)&=\frac{{\text {S}}^{\alpha }(G)}{{\text {M}}^{\alpha }(G)}. \end{aligned}$$

Following a similar reasoning as in the special case where $\alpha = 1$, it is still possible to prove the following inequalities.

Theorem 8

For every fixed positive real number$\alpha$and everyn-vertex graphG, we have

$$\begin{aligned} {\text {avm}}^{\alpha } (E_n) \le {\text {avm}}^{\alpha }(G)\le {\text {avm}}^{\alpha }(K_n). \end{aligned}$$

Moreover, for every real number$\alpha \in (0,1]$and everyn-vertex treeT, we have

$$\begin{aligned}{\text {avm}}^{\alpha }(S_n) \le {\text {avm}}^{\alpha }(T) \le {\text {avm}}^{\alpha }(P_n). \end{aligned}$$

We refer to [11] for more details on the proof. Note that the final inequality (${\text {avm}}^{\alpha }(T) \le {\text {avm}}^{\alpha }(P_n)$) is not generally true for all values of $\alpha$. One can also express the weighted average matching size in terms of the zeros of the matching polynomial:

Lemma 7

LetGbe ann-vertex graph and$\mu _1,\dots ,\mu _n$be the zeros of the matching polynomial ofG. Then

$$\begin{aligned} {\text {avm}}^{\alpha }(G)=\frac{1}{2}\sum _{j=1}^n\frac{\alpha \mu _j^2}{\alpha \mu _j^2+1}. \end{aligned}$$

Finally, it is also possible again to prove inequalities that relate ${\text {avm}}^{\alpha }(G)$ to other invariants. Specifically, we have the following straightforward generalization of Theorem 7:

Theorem 9

For every graphGand every positive real number$\alpha$,

$$\begin{aligned} {\text {ME}}(G)\ge \frac{4}{\sqrt{\alpha }}{\text {avm}}^{\alpha }(G). \end{aligned}$$