REVIEW 1 major objections 4 minor 12 references
On the maximal matchings of trees
T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read For every tree on $n$ vertices, the number of maximal matchings is at least $\lceil n/2\rceil$, with equality only for three families of subdivided stars.
desk verdict A correct new lower bound for maximal matchings in trees with a repairable proof gap in Theorem 3.5; deserves serious refereeing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is a bottom-up labeling $(\alpha_v, \beta_v, \gamma_v)$ for each vertex of a rooted tree. Leaves receive $(1,0,1)$; once all children of $v$ carry labels, set $\alpha_v = \prod_i \beta_{x_i}$, $\beta_v = \sum_i (\prod_{j\ne i}(\alpha_{x_j}+\beta_{x_j}))\gamma_{x_i}$, and $\gamma_v = \prod_i (\alpha_{x_i}+\beta_{x_i})$, where $x_1,\dots,x_k$ are the children of $v$. Then $\Psi(T_u)=\alpha_u+\beta_u$, with $\alpha_u$ counting maximal matchings that leave the root unmatched and $\beta_u$ those that cover it. The proof chain rests on two lemmas: $\alpha_x\le\gamma_x$ for every vertex, with equality only for leaves or vertices whose children are all adjacent to leaves (Lemma 3.1), and the parity theorem (Theorem 3.5) that if deleting any leaf never changes $\Psi$, the tree has even order. These feed an induction splitting on the parity of $n$.
What would settle it
Run the paper's Algorithm 2.2 on every unlabeled tree of order up to, say, 15, and check two things: every tree satisfies $\Psi(T) \ge \lceil n/2\rceil$, and no odd-order tree satisfies $\Psi(T)=\Psi(T-x)$ for every leaf $x$. A single counterexample to either statement would directly refute Theorem 3.12 or Theorem 3.5.
Extended reading notes
Core claim
The central claim, stated as Theorem 3.12, is that for any tree $T$ with $n$ vertices, $\Psi(T) \ge \lceil n/2\rceil$, where $\Psi(T)$ is the number of maximal matchings. Equality holds exactly when $T$ is isomorphic to $S_0(K_{1,(n-1)/2})$ or $S_2(K_{1,(n+1)/2})$ if $n$ is odd, and to $S_1(K_{1,n/2})$ if $n$ is even, where $S_t(K_{1,m})$ is the starlike tree obtained from the star $K_{1,m}$ by subdividing $m-t$ of its edges. The proof supplies a recursive algorithm for computing $\Psi(T)$ on any rooted tree, then proceeds by induction on $n$: for even $n$ it uses the inequality $\Psi(T)\ge\Psi(T-u)$ for a leaf $u$, and for odd $n$ it uses a parity theorem stating that if deleting every leaf leaves $\Psi$ unchanged, the tree order must be even, forcing a strict increase in the odd case. The equality characterization is completed by showing that a minimum tree has exactly one branch vertex and cannot contain certain local configurations such as a vertex adjacent to three leaves or a long pendent path.
Load-bearing premise
The odd-order lower bound relies on the theorem that any tree where deleting every leaf leaves the number of maximal matchings unchanged must have even order, and the proof of that parity theorem invokes a recursive counting argument that is not written out in full.
Editorial extensions
If this is right
- For every $n$, the minimum number of maximal matchings in an $n$-vertex tree is exactly $\lceil n/2\rceil$, so the extremal count grows linearly with the order of the tree.
- The equality cases are completely classified: $S_0(K_{1,(n-1)/2})$ or $S_2(K_{1,(n+1)/2})$ for odd $n$, and $S_1(K_{1,n/2})$ for even $n$; each has exactly one branch vertex.
- Theorem 3.11 shows that a minimum tree has a single branch vertex, and Lemmas 3.7, 3.9, and 3.10 rule out vertices adjacent to three leaves, pendant stars $K_{1,3}$, and pendant paths of length at least four.
- Lemma 3.3, taken from the literature, gives the general inequality $\Psi(T-v)\le\Psi(T)$ for deleting any vertex $v$, with a precise equality condition, and the paper's algorithm makes this inequality effective for computation.
- The counting algorithm itself is a direct method for evaluating $\Psi(T)$ on any tree, bypassing the exponential enumeration of matchings.
Reading between the lines
- The triple-label recursion is essentially a transfer-matrix computation; weighting $\alpha_v$, $\beta_v$, and $\gamma_v$ by variables would produce a generating function for maximal matchings by size or by coverage of specified vertices, a refinement the paper does not pursue.
- The parity theorem (Theorem 3.5) likely has a bijective reformulation: an even-order tree with the property that deleting any leaf preserves $\Psi$ may admit a fixed-point-free involution on its maximal matchings, which would explain the parity without a recursive order argument.
- A natural testable extension is whether the same extremal shape—a single branch vertex with only short pendent paths—also minimizes the number of maximal matchings in trees with a fixed maximum degree or with edge weights; the present theorem covers the unweighted, unbounded-degree case only.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the number Ψ(T) of maximal matchings in a tree T. It presents a dynamic programming algorithm (Algorithm 2.2) that computes Ψ(T) via a three-variable signature (α, β, γ) assigned bottom-up to the vertices of a rooted tree. The main result (Theorem 3.12) is that every n-vertex tree satisfies Ψ(T) ≥ ⌈n/2⌉, with equality characterized by the starlike trees S0(K1,(n−1)/2) or S2(K1,(n+1)/2) when n is odd, and S1(K1,n/2) when n is even. The proof is by induction on n, using a series of lemmas about the behavior of Ψ under leaf deletion and local transformations. A key ingredient is Theorem 3.5, which asserts that if deleting any leaf leaves Ψ unchanged, then the tree has even order.
Significance. If the main theorem is correct, it provides a clean extremal characterization for a natural graph parameter, complementing the known results on the maximum number of maximal matchings in trees. The DP algorithm is a useful and clearly specified tool, and Remark 2.3 correctly verifies the recurrence. The paper is self-contained apart from one imported lemma (Lemma 3.3), and the proof has no free parameters or circularity. The lower bound is sharp with explicit extremal families. The main concern is the completeness of a key parity argument; with a repaired proof of Theorem 3.5, the result would be a solid contribution to extremal combinatorics.
major comments (1)
- [Theorem 3.5] The proof of Claim 2 is incomplete. The sentence "We can recursively prove that |T_z| is even since the order of T is finite" does not constitute a derivation: it gives no induction parameter, no base cases, and no explanation of how the hypothesis Ψ(T)=Ψ(T−x) for every leaf transfers to the subtree T_x^z. This is load-bearing because the odd-n case of Theorem 3.12 relies on the contrapositive: for odd n, some leaf u has Ψ(T) ≥ Ψ(T−u)+1. Without a valid proof of Theorem 3.5, the main theorem is not established for odd n. The authors should supply a complete argument, for example by proving Corollary 3.6 (each inner vertex adjacent to exactly one leaf) via a leaf-propagation argument that uses Claim 1 successively, and then counting leaf-internal incidences to deduce that n is even. As written, Corollary 3.6 is merely asserted as a consequence of the proof of Theorem 3.5, which is exactly the step that is missing.
minor comments (4)
- [Example after Algorithm 2.2] In the worked example of a path P_n rooted at v_n, the signs listed for v3 and v4 appear to be incorrect: starting from v1=(1,0,1), the recurrence gives v3=(1,1,1) and v4=(1,1,2), not (1,1,2) and (1,2,2) as stated. This does not affect the rest of the paper.
- [Lemma 3.9] The phrase "where z is not leave in T" should read "where z is not a leaf in T".
- [Lemma 3.9] The justification for the claim "If the degree of z is two in T, then α_z > 0" is implicit and should be spelled out: if the other neighbor of z were a leaf, then T would have exactly five vertices, contradicting n ≥ 8; hence that neighbor is not a leaf, so β of that neighbor is positive and α_z > 0.
- [Lemma 3.10] In the display for Ψ(T′), the notation N_{T′}(x4)∖{x3,x1} is initially confusing because x3 is a child of x4 in T′ after the transformation; a brief explanatory sentence about the tree structure would improve readability.
Circularity Check
No circularity: the main lower bound is proved by induction from a self-contained counting algorithm; the only imported lemma is an external prior result, not a self-citation.
full rationale
The derivation chain is self-contained. The lower bound in Theorem 3.12 is obtained by induction: for even n, Lemma 3.2 (proved from Algorithm 2.2 and Lemma 3.1) gives Ψ(T) ≥ Ψ(T−u); for odd n, the contrapositive of Theorem 3.5 supplies a leaf with strict increment. Theorem 3.5 is proved from the algorithm's recursion and Observation 1, not from the target inequality. The equality characterization uses Theorem 3.11, which is proved by explicit edge-swap constructions and the external Lemma 3.3 cited from Gorska and Skupien [7]; this is an external result with no author overlap and is not used as a fitted input. The only imported lemma, Lemma 3.3, is a strengthening of the specially proved Lemma 3.2 and is drawn from the literature, not from the authors' prior work. The paper cites the authors' own work [9] only in the introduction as background on benzenoids, not as a load-bearing part of the proof. The handwavy recursive parity sentence in Theorem 3.5 is a proof gap, not circularity: it does not assume the conclusion of the main theorem. No equation reduces to an input by construction.
Assumptions & free parameters
assumptions (1)
- domain assumption Lemma 3.3([7]): For any vertex v in a tree T, Ψ(T-v) ≤ Ψ(T), with equality iff v is a leaf and all other neighbors of its neighbor are adjacent to leaves.
Cite this review
Pith. "Pith review of On the maximal matchings of trees." pith.science (2026). https://pith.science/paper/H5HV6KMF
@misc{pith2026250608557,
author = {Pith},
title = {Pith review of: On the maximal matchings of trees},
year = {2026},
howpublished = {\url{https://pith.science/paper/H5HV6KMF}},
note = {Machine review of arXiv:2506.08557}
}
abstract
An independent edge set of graph $G$ is a matching, and is maximal if it is not a proper subset of any other matching of $G$. The number of all the maximal matchings of $G$ is denoted by $\Psi(G)$. In this paper, an algorithm to count $\Psi(T)$ for a tree $T$ is given. We show that for any tree $T$ with $n$ vertices, $\Psi(T)\geq\lceil\frac{n}{2}\rceil$, and the tree which obtained the lower bound is characterized.
Reference graph
Works this paper leans on
- [1]
-
[2]
T. Biedl, E.D. Demaine, C.A. Duncan, R. Fleischerd and S.G. Kobourov, Tight bounds on maximal and maximum matchings, Discrete Math. 285 (2004) 7–15
work page 2004
-
[3]
T. Doˇ sli´ c, T. Short, Maximal matchings in polyspiro and benzenoid chains, Appl. Anal. Discrete Math. 15 (2021) 179–200
work page 2021
-
[4]
Doˇ sli´ c, Saturation number of fullerene graphs, J
T. Doˇ sli´ c, Saturation number of fullerene graphs, J. Math. Chem. 43 (2008) 647–657
work page 2008
-
[5]
T. Doˇ sli´ c, I. Zubac, Saturation number of benzenoid graphs, MATCH Commun. Math. Comput. Chem. 73 (2015) 491–500
work page 2015
-
[6]
T. Doˇ sli´ c, I. Zubac, Counting maximal matchings in linear polymers, Ars Math. Contemp. 11 (2016) 255–276
work page 2016
-
[7]
J. G´ orska, Z. Skupie´ n, Trees with maximum number of maximal matchings, Discrete Math. 307 (2007) 1367–1377
work page 2007
-
[8]
Klazar, Twelve Countings with Rooted Plane Trees, European J
M. Klazar, Twelve Countings with Rooted Plane Trees, European J. Combin. 18 (1997) 195–210
work page 1997
Show all 12 references
-
[9]
L. Shi, K. Deng, Counting the maximal and perfect matchings in benzenoid chains, Appl. Math. Comput. 447 (2023), Paper No. 127922, 11 pp
2023
-
[10]
Short, The saturation number of carbon nanocones and nanotubes, MATCH Commun
T. Short, The saturation number of carbon nanocones and nanotubes, MATCH Commun. Math. Comput. Chem. 82 (2019) 181–201
2019
-
[11]
Tratnik, P
N. Tratnik, P. ˇZPleterˇ sek, Saturation number of nanotubes, Ars Math. Contemp. 12 (2017) 337–350. 13
2017
-
[12]
Wagner, On the number of matchings of a tree, European J
S.G. Wagner, On the number of matchings of a tree, European J. Combin. 28 (2007) 1322– 1330. 14
2007
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.