The number of maximal matchings in polygon rings

Chengqi Li; Jinhui Yin; Lingjuan Shi

REVIEW 3 major objections 4 minor 12 references

The number of maximal matchings in polygon rings

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The number of maximal matchings in a hexagonal ring is the trace of a product of 9x9 matrices chosen from S, L, and R.

desk verdict Hexagon-ring trace formula is probably right and worth publishing, but the polygon-ring extension rests on an unproved algorithm and needs verification. read the letter →

arxiv 2506.08687 v1 pith:JPRUFTHA submitted 2025-06-10 math.CO

Chengqi Li , Jinhui Yin , Lingjuan Shi This is my paper

classification math.CO MSC 05C7005A15

keywords maximalmatchingpolygonringshexagonaltransitionmatrixtraceformulaenumeration

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

A maximal matching cannot be enlarged by adding any edge, and counting them in a ring is awkward because a ring has no natural starting point. This paper proves that for a hexagonal ring with $n$ hexagons, the count $\Psi(H)$ equals the trace of the product of $n$ $9\times 9$ matrices, one per hexagon, where the matrix is one of three fixed 0-1 matrices $S$, $L$, or $R$ according to how that hexagon connects to its neighbours. The same trace formula is extended to rings whose faces are arbitrary polygons, with the per-face matrices produced by an explicit algorithm. The result turns a combinatorial enumeration problem into a small matrix computation that yields exact counts without listing matchings. The paper's worked examples are exact: $2804280$ for an 11-hexagon ring and $481614$ for a 9-polygon ring.

What carries the argument

The maximal matching vector $\Psi_{xy}(G)$ is a nine-component column vector whose entries count maximal matchings of $G$ under nine conditions on the boundary vertices $x$ and $y$: unconstrained, with $x$ or $y$ removed, with both removed, with both required to be covered, and the four asymmetric combinations. The transfer matrices $S$, $L$, $R$, taken from the earlier chain result, propagate this vector along a hexagonal chain. For the ring, the chain is torn along edge $dc$, the graph $F$ is formed by gluing an arbitrary subgraph $K$ to the tear, and the nine decomposition lemmas (Lemmas 2.3–2.11) convert each boundary case into a column of the product matrix, so the closed ring corresponds to summing the diagonal, i.e., the trace. For general polygon rings, Algorithm 3.2 constructs the analogous $9\times 9$ transition matrix $T_{m,i}$ by listing the maximal matchings of a single $m$-gon with two distinguished edges and sorting them into the nine boundary categories.

What would settle it

Enumerate all maximal matchings by brute force for every hexagonal ring with a fixed small number of hexagons, for example all $3^6$ type sequences with $n=6$, and compare each count with the trace of the corresponding matrix product; any mismatch would refute Theorem 1.1. Independently, verify the nine identities in Lemmas 2.3–2.11 on the two-hexagon terminal subgraph $D$ for each of the three connection modes, and check Algorithm 3.2's matrices against direct computation of $\Psi_{ab}(Z)$ on small polygon chains.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for a hexagonal ring $H$ with type $M_1 M_2 \cdots M_n$, where each $M_i$ is $t(1)$, $t(2)$, or $t(3)$, the number of maximal matchings is $\Psi(H)=\operatorname{tr}(\prod_{i=1}^{n} f(M_i))$, with $f(t(1))=L$, $f(t(2))=S$, $f(t(3))=R$. The proof tears the ring open along a shared edge to form a hexagonal chain, attaches an arbitrary subgraph to the two open ends, and classifies the maximal matchings of this auxiliary graph into nine cases by whether the two boundary edges $ed$ and $fc$ are included and whether the vertices $e$ and $f$ are covered. Nine lemmas (Lemmas 2.3–2.11) show that each case contributes exactly one diagonal entry of the product matrix $M=\prod_i f(M_i)$, so summing the cases gives the trace. Theorem 1.2 asserts the identical trace formula for arbitrary polygon rings, where each face's matrix $T_{s_i,j}$ is generated by Algorithm 3.2; the paper computes two examples as exact values.

Load-bearing premise

The load-bearing premise is that the unproved terminal identities asserted in Lemmas 2.3–2.11 hold for all three hexagon connection modes, and that Algorithm 3.2 correctly produces the transition matrices $T_{m,i}$, because every diagonal entry of the product matrix used in the trace is built from those steps.

Editorial extensions

If this is right

For a hexagonal ring of any length, $\Psi(H)$ can be computed by multiplying $n$ $9\times 9$ matrices and taking the trace, giving an $O(n)$ algorithm with exact integer output.
The same trace product works for rings with arbitrary polygonal faces once the finite family of matrices $T_{m,i}$ is generated for the face sizes appearing in the ring.
The count depends only on the cyclic sequence of connection types, not on the geometric embedding, so topologically equivalent rings have identical maximal matching numbers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct brute-force enumeration of maximal matchings on small hexagonal rings (say $n \le 10$) and comparison with the trace formula would test the unproved terminal identities on which the proof depends.
If the nine-state vector collapse works here, the same tearing-and-gluing trace argument may transfer to other planar 2-connected graphs whose faces meet their neighbours along single edges, such as rings of squares or mixed polygons.
Symmetries of the matrices $S$, $L$, $R$ (and of the $T_{m,i}$) would imply congruences or identities among maximal matching counts of rings related by rotations or reflections; the paper does not explore these.
The transfer-matrix form also suggests studying growth rates of $\Psi$ for families of rings as $n$ grows, governed by the spectral behaviour of the matrix product.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

The one thing to know: the hexagon-ring result (Theorem 1.1) is the real content and looks right; the polygon-ring result (Theorem 1.2) is not proved. The proof of Theorem 1.2 is omitted in one sentence, and Lemma 3.1 — the lemma that justifies Algorithm 3.2 — is asserted as “clearly holds.” That is a load-bearing hole, not a cosmetic one.

What is genuinely new: a trace formula for maximal matchings in hexagonal rings. It is a transfer-matrix closure result, and the underlying matrices come from the authors’ own earlier chain paper [11], but I do not see this particular formula in the cited chain/tree literature. The self-citation is transparent and not circular. The trace identification is structurally plausible: the nine subcases in Section 2.2 map to the diagonal entries of M, and the end-swap symmetry of the two torn ends is consistent with that assignment. The numerical example (2804280) is a finite check; I have no reason to doubt it.

Soft spots, in proportion: the nine lemmas in Section 2.1 actually prove only the first component and then say the rest follows by the same analysis. For a paper whose entire theorem depends on those vector components, that is too much “easy to check.” I also cannot reconcile the factor Ψ(K−d|c) in SubCase 2.2 with the component decomposition spelled out there; it may be a typo, but it should be fixed. These are minor-to-moderate issues.

The bigger problem is Theorem 1.2 and Algorithm 3.2. The algorithm’s nine cases are not shown to be exhaustive or disjoint, and the proof of Lemma 3.1 is one line. The abstract’s central promise is the arbitrary polygon-ring formula, so omitting that proof is not a small matter. No code or machine-readable matrices are shipped, so there is nothing to independently verify short of reimplementing the algorithm by hand.

Who this is for: people who count matchings in chemical graphs, and exact enumerators generally. I would send it to a serious referee, with a clear instruction: either complete Section 3 or re-scope the paper to hexagonal rings. I would also want brute-force checks on small polygon rings before accepting the general claim.

Candidly, I would accept a revision that fixes the proof of the hexagon case and either proves or cuts Theorem 1.2. Right now the paper is one solid theorem plus one unverified claim.

Referee Report

3 major / 4 minor

Summary. The paper studies the number of maximal matchings in polygon rings, i.e., planar graphs obtained by cyclically gluing polygon chains. For hexagonal rings the authors state (Theorem 1.1) that the number of maximal matchings equals the trace of a product of 9-by-9 matrices S, L, and R assigned according to the connection types t(1), t(2), t(3), and they illustrate this with the value 2804280 for the ring in Fig. 2(b). The proof tears the ring along an edge into a hexagonal chain, introduces an auxiliary graph F, and decomposes maximal matchings into nine cases according to the status of the two edges ed and fc (Lemmas 2.3–2.11), each case contributing one diagonal entry of the product matrix M. The paper then extends the claim to arbitrary polygon rings (Theorem 1.2), introducing Algorithm 3.2 to generate 9-by-9 transition matrices T_{m,i} for each face size and connection type, and reports the value 481614 for the polygon ring in Fig. 1. The polygonal extension is stated without proof: Theorem 1.2 is justified only by 'So we omit its proof here,' and its foundational Lemma 3.1 is justified by a one-sentence appeal to Algorithm 3.2.

Significance. If the results are correct, they provide a compact and purely combinatorial transfer-matrix formula for maximal matchings of hexagonal and general polygon rings, with no fitted parameters and with exact numerical predictions. The explicit 9-by-9 matrices, the worked examples, and the absence of circularity are genuine strengths; the paper also builds transparently on the authors' earlier work [11]. However, the correctness of the main theorems currently rests on several unproved or underproved finite checks: the terminal two-hexagon identities in Lemmas 2.3–2.11 and the correctness of Algorithm 3.2 for arbitrary polygons. These are load-bearing rather than cosmetic: they determine the entries of the transfer matrices, and hence every value computed from the trace formula. Because these gaps appear fillable by supplying detailed verifications or a machine-checked certificate, the appropriate outcome is revision rather than rejection.

major comments (3)

[§2.1, Lemmas 2.3–2.11 and Eq. (2)] The proof of Theorem 1.1 depends on nine lemmas whose terminal-hexagon identities are asserted rather than proved. For example, in Lemma 2.3 the three possible positions of the shared edge uv in the two-hexagon graph D are dismissed with 'it is easy to check that Ψ_xy(D) = f(M_{n-1}) f(M_n) e_4' (and similarly for the other cases in Lemmas 2.4–2.11). These identities determine the columns of the matrix M, and every diagonal entry summed in Eq. (2) is obtained from exactly one of them. The current manuscript gives no derivation and no explicit enumeration for these checks, so the proof of Theorem 1.1 is incomplete as written.
[§3, Lemma 3.1] Lemma 3.1, the transfer-matrix statement for arbitrary polygon chains, is proved only by the sentence 'By the process of the Algorithm 3.2, this conclusion clearly holds.' This is not a proof. Algorithm 3.2 must establish three nontrivial facts: every maximal matching of the combined graph decomposes uniquely into a maximal matching of J1 and a maximal matching of K; the nine case conditions in steps (5.10.1)–(5.10.9) are exhaustive and disjoint; and the assigned column y is exactly the corresponding component of Ψ_{dc}(K). None of these is demonstrated, and the matrices T_{m,i} in Table 3.1 are therefore unsupported.
[§3, Theorem 1.2] Theorem 1.2 is the stated extension of the trace formula to arbitrary polygon rings, but its proof is explicitly omitted: 'So we omit its proof here.' Since Theorem 1.2 depends on Lemma 3.1 and Algorithm 3.2, neither of which is proved, the central claim for arbitrary polygon rings is not established in the manuscript. The computed sample value 481614 for the ring in Fig. 1 rests on these unverified matrices, so its correctness cannot currently be assessed.

minor comments (4)

[Tables 2.1 and 3.1] Both tables are announced but no actual data appear in the manuscript; readers cannot reproduce the claimed checks from the tables.
[Throughout] There are several typos and notational slips, including 'maxiaml' in Lemma 2.4, 'Algprithm' in Section 3, and inconsistent use of 'trp' for trace; these should be corrected.
[Theorem 1.2] The range 'tps_i, si−4q' is confusing and appears inconsistent with the earlier definition k_j ∈ [1, s_j−3]; for s_i = 4 this would include an invalid index 0.
[Algorithm 3.2, step 5.10] The comments explaining the sets R, V, and V' are difficult to follow and should be rewritten as a precise definition, since the correctness of the column assignment depends on them.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular reduction: the hexagonal trace formula is derived from published chain transfer matrices and new local lemmas; the polygon-ring extension rests on omitted proofs, but not on circularity.

full rationale

The claimed derivation is not circular. Theorem 1.1 is obtained by tearing the hexagonal ring along dc, applying the chain transfer matrices S, L, R from the authors' earlier published paper [11] (Theorems 2.1-2.2), decomposing maximal matchings of the auxiliary graph F into nine cases (Lemmas 2.3-2.11), and identifying each diagonal entry of M = product_i f(M_i) with one of the nine subcase counts; Equation (2) then sums these entries to tr(M). The local terminal-hexagon identities in Lemmas 2.3-2.11 are asserted as 'easy to check' or 'we can check' finite computations, but they do not presuppose the trace formula: they compute restricted maximal-matching vectors of the two-hexagon subgraph D and thereby determine the relevant columns of M. Thus the diagonal entries are derived, not fitted. No parameter is fitted to the final counts, and the printed values (2804280 and 481614) are computed from the stated matrices. The only self-citation is [11], which is transparent and supplies the chain-level transfer matrices; it is external published support rather than an unverified self-referential premise. The polygon-ring extension is less rigorously supported: Lemma 3.1 is justified only by 'By the process of the Algorithm 3.2, this conclusion clearly holds' and Theorem 1.2 by 'So we omit its proof here.' These are genuine proof gaps and a correctness risk, because Algorithm 3.2's nine-case classification and column assignments must be exhaustive and faithful for the trace formula to hold, but they are not circular: the algorithm defines T_{m,i} by enumerating matchings of the modified polygon J1 independently of the ring count. Overall circularity score is 1.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted or hand-tuned parameters appear; all counts are exact and the matrices are printed in full. The ledger instead records five imported or asserted premises: disjoint-union multiplicativity (standard), the chain transfer-matrix theorems imported from the authors' own prior paper [11], the exhaustiveness of the 9-subcase partition, the unproved terminal-hexagon identities inside the nine lemmas, and the correctness of Algorithm 3.2 plus Theorem 1.2, which the text itself marks as unproven.

assumptions (5)

standard math Disjoint-union multiplicativity: Psi(G) = Psi(G1) * Psi(G2) when G is the disjoint union of G1 and G2.
Stated in Section 2 ('any maximal matching of G is consisted of a maximal matching of G1 and a maximal matching of G2') and invoked in every lemma to split F into the G-part and the K-part.
domain assumption Transfer-matrix identities of Theorem 2.1 and the chain formula of Theorem 2.2, imported from ref. [11]: Psi_ab(G) = S * Psi_dc(W), Psi_ga(G) = L * Psi_dc(W), Psi_bf(G) = R * Psi_dc(W).
Quoted without proof from Shi-Deng [11], which shares the corresponding author; the present ring proof is built directly on these identities and on the S, L, R matrix entries.
domain assumption The 9-state maximal-matching vector is a complete boundary description: a maximal matching of the ring is captured by one of the nine subcases of Section 2.2, with no overcounting.
The proof of Theorem 1.1 partitions maximal matchings of H by membership of edges ed, fc and coverage of e, f; exhaustiveness and disjointness are asserted from the geometry of Fig. 4 and are not verified in the text.
ad hoc to paper Terminal-hexagon computations in Lemmas 2.3-2.11: e.g. Psi_xy(D) = f(M_{n-1}) * f(M_n) * e_4 in all three connection modes (Lemma 2.3), with analogous identities for e_2, e_6, e_3, e_7, e_1, e_9, e_8, e_5 in the other lemmas.
Asserted as 'easy to check' and 'for the three cases... we can check' without demonstration; these identities determine every column of the matrix product M used in the trace.
ad hoc to paper Algorithm 3.2 computes the transfer matrices T_{m,i} correctly (Lemma 3.1), and the conclusion extends to all polygon rings (Theorem 1.2).
Lemma 3.1's proof is one sentence ('By the process of the Algorithm 3.2, this conclusion clearly holds') and Theorem 1.2's proof is omitted ('So we omit its proof here').

how reviews work

0 comments

Cite this review

Pith. "Pith review of The number of maximal matchings in polygon rings." pith.science (2026). https://pith.science/paper/JPRUFTHA

@misc{pith2026250608687,
  author       = {Pith},
  title        = {Pith review of: The number of maximal matchings in polygon rings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JPRUFTHA}},
  note         = {Machine review of arXiv:2506.08687}
}

abstract

A matching of graph $G$ is maximal if it cannot be expanded by adding any edge to create a larger matching. In this paper, for a hexagonal ring $H$ with $n$ hexagons, we show that the number of maximal matchings of $H$ equals to the trace of the product of $n$ matrices, each of which is $S$, $L$, or $R$ according to the type of the connection mode of $H$. Finally, we extend this conclusion to arbitrary polygon rings and provide an algorithm to determine the transition matrices of polygon chains (rings).

Figures

Figures reproduced from arXiv: 2506.08687 by the authors.

**Figure 2.** Examples for hexagon chain and hexagon ring. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** The graph in Theorem 2.1. The following two Theorems computed the cases for hexagonal chains. Theorem 2.1 ([11]). For the graph G as depicted in [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Graphs H, G and auxiliary graph F In the following, the graphs H, F and G are as depicted in [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

**Figure 5.** Figure 5: Graph Z 1. Input m, i 2. Create an m-sided polygon J based on the value of m, arbitrarily select one of the sides as ab, and determine the side dc according to the connection type tpm, iq. 3. Subtract dc from the polygon J, add a new neighbor k1 for d, and add a new ne…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[11]

Shi and K

L. Shi and K. Deng. Counting the maximal and perfect matchings in benzenoid chains. Applied Mathematics and Computation, 447:127922, 2023

work page 2023
[1]

R. Cruz, C. Mar ´ ın, and J. Rada. Computing the hosoya index of catacondensed hexagonal systems.MATCH Commun. Math. Comput. Chem, 77(3):749–764, 2017

work page 2017
[2]

Cyvin and I

S. Cyvin and I. Gutman. Kekul´ e structures in benzenoid hydrocarbons, volume 46 of. Lecture Notes in Chemistry, 1988

work page 1988
[3]

Doˇ sli´ c and T

T. Doˇ sli´ c and T. Short. Maximal matchings in polyspiro and benzenoid chains.Applicable Analysis and Discrete Mathematics, 15(1):179–200, 2021

work page 2021
[4]

Doˇ slic and I

T. Doˇ slic and I. Zubac. Saturation number of benzenoid graphs.MATCH Commun. Math. Comput. Chem, 73:491–500, 2015

work page 2015
[5]

Doˇ slic and I

T. Doˇ slic and I. Zubac. Counting maximal matchings in linear polymers.Ars Math. Contemp, 11:255–276, 2016. 20

work page 2016
[6]

Z. Galil. Efficient algorithms for finding maximum matching in graphs.ACM Computing Surveys (CSUR), 18(1):23–38, 1986

work page 1986
[7]

G´ orska and Z

J. G´ orska and Z. Skupie´ n. Trees with maximum number of maximal matchings.Discrete mathematics, 307(11-12):1367–1377, 2007

work page 2007

Show all 12 references

[8]

M. Klazar. Twelve countings with rooted plane trees.European Journal of Combinatorics, 18(2):195–210, 1997

1997
[9]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer. Matching theory, vol. 29.Annals of Discrete Mathematics, North-Holland, Amsterdam, 1986

1986
[10]

M. S. Oz and I. N. Cangul. Computing the merrifield-simmons indices of benzenoid chains and double benzenoid chains.Journal of Applied Mathematics and Computing, 68(5):3263– 3293, 2022

2022
[12]

H. A. Staab, F. Diederich, and V. ˇCaplar. Cycloarenes, a new class of aromatic compounds, iii. studies towards the synthesis of cyclo [dedeededee] decakisbenzene.Liebigs Annalen der Chemie, 1983(12):2262–2273, 1983. 21

1983

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [11]

Shi and K

L. Shi and K. Deng. Counting the maximal and perfect matchings in benzenoid chains. Applied Mathematics and Computation, 447:127922, 2023

work page 2023

[2] [1]

R. Cruz, C. Mar ´ ın, and J. Rada. Computing the hosoya index of catacondensed hexagonal systems.MATCH Commun. Math. Comput. Chem, 77(3):749–764, 2017

work page 2017

[3] [2]

Cyvin and I

S. Cyvin and I. Gutman. Kekul´ e structures in benzenoid hydrocarbons, volume 46 of. Lecture Notes in Chemistry, 1988

work page 1988

[4] [3]

Doˇ sli´ c and T

T. Doˇ sli´ c and T. Short. Maximal matchings in polyspiro and benzenoid chains.Applicable Analysis and Discrete Mathematics, 15(1):179–200, 2021

work page 2021

[5] [4]

Doˇ slic and I

T. Doˇ slic and I. Zubac. Saturation number of benzenoid graphs.MATCH Commun. Math. Comput. Chem, 73:491–500, 2015

work page 2015

[6] [5]

Doˇ slic and I

T. Doˇ slic and I. Zubac. Counting maximal matchings in linear polymers.Ars Math. Contemp, 11:255–276, 2016. 20

work page 2016

[7] [6]

Z. Galil. Efficient algorithms for finding maximum matching in graphs.ACM Computing Surveys (CSUR), 18(1):23–38, 1986

work page 1986

[8] [7]

G´ orska and Z

J. G´ orska and Z. Skupie´ n. Trees with maximum number of maximal matchings.Discrete mathematics, 307(11-12):1367–1377, 2007

work page 2007