arxiv: 2605.13198 · v1 · submitted 2026-05-13 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Size and spectral conditions for a graph with given minimum degree to be k-d-critical

Zhenhao Zhang , Xiaogang Liu , Ligong Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-14 18:31 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C70

keywords k-matchingk-d-criticalspectral radiusminimum degreeBerge-Tutte formulafactor-criticalbicriticalgraph size

0 comments

The pith

A graph with minimum degree δ is k-d-critical if its size or spectral radius meets a sharp threshold depending on δ, k and n.

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

The paper establishes sharp lower bounds on the number of edges and on the spectral radius that force a graph of minimum degree δ to be k-d-critical, generalized factor-critical, or generalized bicritical. These notions rest on k-matchings, which assign each edge an integer weight from 0 to k without exceeding total weight k at any vertex. A k-d-critical graph allows, for every vertex v, a k-matching whose total weight falls short by exactly d at v while reaching the maximum k everywhere else; the generalized versions require that the empty set alone maximizes the deficiency in the k-Berge-Tutte formula. If the size or spectral conditions hold, every vertex can serve as the unique site of deficiency d.

Core claim

For a graph G with minimum degree δ, if the size meets or exceeds the stated extremal function of n, δ, k and d (with d ≡ n mod 2), or if the spectral radius meets the corresponding bound, then G is k-d-critical. The same style of sharp bounds applies to generalized factor-critical graphs of odd order and generalized bicritical graphs of even order, both characterized by uniqueness of the maximizing set in the k-Berge-Tutte formula.

What carries the argument

The k-matching that realizes exact deficiency k-d at one prescribed vertex while saturating all others to weight k, which directly encodes the k-d-critical property via the k-Berge-Tutte formula.

If this is right

Every vertex admits a k-matching with deficiency exactly d at that vertex and full saturation elsewhere.
The spectral-radius condition implies the size condition through standard eigenvalue-edge inequalities.
Generalized factor-critical graphs are exactly those of odd order where the k-Berge-Tutte maximum is attained solely by the empty set.
The bounds are attained by certain non-critical extremal graphs, confirming sharpness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The conditions supply a polynomial-time check for the critical properties once δ and k are fixed, via computing the number of edges or the largest eigenvalue.
Similar spectral arguments may extend the results to the setting of fractional k-matchings or to hypergraph matchings.
High spectral radius under minimum degree may force the k-Berge-Tutte formula to behave like the classical Tutte-Berge formula in dense random graphs.

Load-bearing premise

The parity condition d ≡ n mod 2 together with the existence of a k-matching that achieves the exact deficiency pattern at every single vertex.

What would settle it

Exhibit a graph G of order n and minimum degree δ whose size or spectral radius meets the paper's bound yet, for some vertex v, no k-matching leaves deficiency exactly d at v while saturating every other vertex.

read the original abstract

A $k$-matching in a graph $G$ is defined as a function $f:E(G) \rightarrow \{0,1,\ldots,k\}$ satisfying $\sum_{e\in E_G(v)} f(e)$ $\leq k$ for each vertex $v\in V(G)$, where $E_G(v)$ denotes the set of edges incident to $v$ in $G$. For $1\leq d\leq k$ and $d \equiv |V(G)|~(\mathrm{mod}~2)$, if for any $ v \in V(G)$, there exists a $k$-matching $f$ such that $\sum_{e\in E_G(v)}f(e)=k-d$ and $\sum_{e\in E_G(u)}f(e)=k \text{ for any } u\in V(G)-\{v\}$, then $G$ is $k$-$d$-critical. A graph $G$ of odd order (resp. even order) is generalized factor-critical (resp. generalized bicritical) if the empty set is the unique set attaining the maximum value in $k$-Berge-Tutte-formula of $G$. In this paper, we provide sharp sufficient conditions in terms of size or spectral radius respectively for a graph $G$ to be $k$-$d$-critical, generalized factor-critical and generalized bicritical with minimum degree.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives sharp size and spectral-radius bounds that force k-d-criticality (and the generalized factor/bicritical cases) under a minimum-degree hypothesis, using standard matching-theory machinery.

read the letter

The main point is that the authors supply explicit sufficient conditions on the number of edges or the spectral radius which, together with a fixed minimum degree, guarantee that a graph is k-d-critical. The same style of bound is given for the generalized factor-critical and bicritical versions. They work from the k-matching definition (an edge weighting bounded by k at each vertex) and the k-Berge-Tutte maximizer, and they require the usual parity condition on order and deficiency d. The bounds are claimed to be sharp, which is the concrete contribution here. What the paper does cleanly is turn the abstract matching-deficiency property into checkable numerical or eigenvalue thresholds that a reader can apply without enumerating all k-matchings. The minimum-degree assumption is used to control the possible deficiencies, and the spectral part presumably leans on the usual Perron-vector counting. That combination is new enough to be worth recording. The soft spots are modest. The abstract gives no proof outline, so it is impossible to see exactly how the eigenvalue bound is turned into the required deficiency pattern at every vertex; one would want to check that the argument does not lose tightness when the graph is not regular. The reliance on the k-Berge-Tutte formula is standard rather than circular, but the sharpness examples are not shown in the abstract, so the reader has to take the authors' word that the bounds cannot be improved. Overall the work is incremental but technically grounded. It is aimed at people who already work with matching-critical graphs and want usable sufficient conditions rather than full characterizations. A specialist in spectral graph theory or extremal matching theory would get value from the explicit bounds. I would send it to peer review; the claims are specific and the area is active enough that referees can verify the derivations without much trouble.

Referee Report

0 major / 2 minor

Summary. The manuscript defines a k-matching as an edge function f to {0,1,...,k} with degree sum at most k at each vertex. It introduces k-d-critical graphs (1 ≤ d ≤ k, d ≡ |V(G)| mod 2) as those for which every vertex v admits a k-matching with exact deficiency d at v and saturation k at all other vertices. Generalized factor-critical (odd order) and generalized bicritical (even order) graphs are defined as those where the empty set is the unique maximizer in the k-Berge-Tutte formula. The central results supply sharp sufficient conditions on the number of edges and on the spectral radius, under a minimum-degree hypothesis, that force a graph to satisfy one of these three criticality properties.

Significance. If the derivations are correct, the work supplies new extremal and spectral criteria that characterize matching-critical graphs with prescribed minimum degree. The explicit use of the k-Berge-Tutte maximizer and standard Perron-vector arguments for the spectral bounds aligns with classical matching theory while adding quantitative size and eigenvalue thresholds; the claimed sharpness, once verified by extremal constructions, would make the bounds tight and therefore directly applicable to further extremal questions in the area.

minor comments (2)

[Abstract] Abstract: the sharpness assertion is stated without any reference to the extremal graphs or the form of the bound; a single sentence indicating the extremal examples (e.g., complete graphs or near-complete graphs of appropriate order) would make the claim immediately verifiable from the abstract.
[Preliminaries] The notation for the k-Berge-Tutte formula is introduced without an explicit displayed equation; adding the standard formula (with the deficiency sum over odd components) in the preliminary section would clarify the subsequent definitions of generalized factor-critical and bicritical graphs.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our manuscript and the positive assessment of its significance. The recommendation for minor revision is noted. As no specific major comments appear in the report, we have no point-by-point revisions to address at present and believe the current version is ready for publication subject to any editorial suggestions.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper defines k-d-critical, generalized factor-critical and generalized bicritical graphs directly from the k-matching function and the k-Berge-Tutte maximizer (standard external notions). It then supplies explicit size and spectral-radius thresholds that force the required deficiency pattern at every vertex. These thresholds are obtained via ordinary double-counting arguments and Perron-vector inequalities under the given minimum-degree hypothesis; no equation reduces a claimed prediction to a fitted input, no load-bearing step collapses to a self-citation, and no ansatz is smuggled in. The central claims therefore remain independent of the paper's own results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard k-Berge-Tutte formula and the parity condition; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math The k-Berge-Tutte formula gives the maximum deficiency value attained by any k-matching.
Invoked to define generalized factor-critical and bicritical graphs.

pith-pipeline@v0.9.0 · 5555 in / 1208 out tokens · 32037 ms · 2026-05-14T18:31:01.540863+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

A k-matching ... sum f(e) ≤ k ... k-d-critical if for any v there exists f with sum_v = k-d and sum_u =k for u≠v
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

GFCk / GBCk defined via unique k-barrier being empty set; size/spectral conditions via K_s ∨ (K_{n-2s}+K_s)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

Berman, R.J

A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979. 12

work page 1979
[2]

Brouwer, W.H

A.E. Brouwer, W.H. Haemers, Spectra of Graphs, Springer, Berlin, 2011

work page 2011
[3]

Chang, Y

C.B. Chang, Y. Liu, Y.P. Qiu, Generalized factor-critical graphs and bicritical graphs about integerk-matching, Discrete Appl. Math. 378 (2026) 762-770

work page 2026
[4]

D.D. Fan, S. Goryainov, X.Y. Huang, H.Q. Lin, The spanningk-trees, perfect matchings and spectral radius of graphs, Linear Multilinear Algebra 70(21) (2022) 7264-7275

work page 2022
[5]

Godsil, G

C. Godsil, G. Royle, Algebraic Graph Theory, Springer-Verlag, NewYork, 2001

work page 2001
[6]

Liu, X.H

Y. Liu, X.H. Liu, Integerk-matchings of graphs, Discrete Appl. Math. 235 (2018) 118-128

work page 2018
[7]

Liu, X.L

Y. Liu, X.L. Su, D.N. Xiong, Integerk-matchings of graphs:k-Berge-Tutte formula,k- factor-critical graphs andk-barriers, Discrete Appl. Math. 297 (2021) 120-128

work page 2021
[8]

H.L. Lu, W. Wang, On perfectk-matchings, Graphs Combin. 30 (2014) 229-235

work page 2014
[9]

Niu, S.S

M.Y. Niu, S.S. Zhang, X.M. Wang, Perfectk-matching,k-factor-critical andA α-spectral radius, Discrete Appl. Math. 376 (2025) 384-393

work page 2025
[10]

O, Spectral radius and matchings in graphs, Linear Algebra Appl

S. O, Spectral radius and matchings in graphs, Linear Algebra Appl. 614 (2021) 316-324

work page 2021
[11]

Tutte, The 1-factors of oriented graphs, Proc

W.T. Tutte, The 1-factors of oriented graphs, Proc. Am. Math. Soc. 4 (1953) 922-931

work page 1953
[12]

Zhang, D.D

Q.B. Zhang, D.D. Fan, Perfect integerk-matching,k-factor-critical, and the spectral radius of graphs, Linear Algebra Appl. 701 (2024) 97-111

work page 2024
[13]

Zhang, H.Q

Y.K. Zhang, H.Q. Lin, Perfect matching and distance spectral radius in graphs and bipartite graphs, Discrete Appl. Math. 304 (2021) 315-322

work page 2021
[14]

Zhang, H.Q

Y.K. Zhang, H.Q. Lin, Q.H. Liu, J.F. Zheng, Distance spectrum, 1-factor and vertex-disjoint cycles, Linear Algebra Appl. 654 (2022) 10-27

work page 2022
[15]

Zhao, X.Y

Y.H. Zhao, X.Y. Huang, Z.W. Wang, TheA α-spectral radius and perfect matchings of graphs, Linear Algebra Appl. 631 (2021) 143-155

work page 2021
[16]

Zheng, S.C

L. Zheng, S.C. Li, X.B. Luo, G.F. Wang, Some sufficient conditions for a graph with mini- mum degree to bek-factor-critical, Discrete Appl. Math. 348 (2024) 279-291. 13

work page 2024