Spectral conditions for graphs to contain $k$-factors

Wenqian Zhang; Xinying Tang

REVIEW 3 major objections 3 minor 1 cited by

Spectral conditions for graphs to contain $k$-factors

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

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

Pith's one-line read A sharp spectral-radius threshold guarantees k-factors in all sufficiently large graphs of minimum degree at least k.

desk verdict The extremal graph G_{n,k} actually has a k-factor, so the sharpness example and the main theorem collapse; the proof structure is plausible but the central construction is wrong. read the letter →

arxiv 2508.05678 v1 pith:7UVWZJBB submitted 2025-08-05 math.CO

Xinying Tang , Wenqian Zhang This is my paper · ORCID

classification math.CO MSC 05C5005C70

keywords spectralradiusk-factoradjacencymatrixminimumdegreeextremalgraphbindingnumberjoinofcliquesf-factortheorem

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

This paper tries to identify, by its spectral radius alone, when a graph is guaranteed to contain a k-factor, a spanning subgraph in which every vertex has degree exactly k. The proposed answer is a sharp threshold: for k ≥ 2, kn even, and n at least roughly k² + 6k + 7 or 20k + 10, every n-vertex graph with minimum degree at least k and spectral radius at least ρ(G_{n,k}) must contain a k-factor, unless it is exactly the extremal graph G_{n,k}. The extremal graph is built from three cliques: K_k joined to K_{k+1} ∪ K_{n−1−2k}, with k−1 extra edges from one vertex of the middle clique to vertices of the largest clique. If the theorem is right, checking one eigenvalue settles a problem on 1-binding graphs that was previously open for general k.

What carries the argument

The machinery has three parts. The first is the f-factor theorem in the form of Lemma 2.4, which converts 'no k-factor' into an inequality on pairs of disjoint vertex sets S and T. The second is a spectral edge-switching lemma that compares Perron-vector entries and says that moving an edge from a smaller-weight position to a larger-weight position strictly increases the spectral radius; this is what forces the extremal obstruction to be a join of cliques with neatly ordered Perron entries. The third is the extremal object itself, G_{n,k}, the join K_k ∨ (K_{k+1} ∪ K_{n−1−2k}) with k−1 added edges; its spectral radius is the threshold that runs through the whole statement.

What would settle it

Construct an explicit k-factor of G_{n,k} for any admissible k and n, say k = 2 and n = 50: the clique K_{k+1} alone is k-regular and the remaining clique has order at least k + 1, so a spanning k-regular subgraph can be assembled by combining a k-factor of K_{k+1} with a k-factor of the large clique. If such a construction succeeds, the sharpness assertion of the paper is false even though the sufficiency theorem may remain true.

Watch

Extended reading notes

Core claim

The central discovery is that the spectral radius of the specific graph G_{n,k} = K_k ∨ (K_{k+1} ∪ K_{n−1−2k}) plus k−1 cross edges is the cutoff for k-factor existence among n-vertex graphs with minimum degree at least k. The proof works by contraposition: if G has no k-factor, the f-factor theorem supplies disjoint vertex sets S, T whose counts violate the factor condition; that violation puts G into a family of obstruction graphs. An edge-switching argument with Perron vectors shows that within this family the spectral radius is maximized uniquely by G_{n,k}. Hence any graph with ρ(G) ≥ ρ(G_{n,k}) cannot be a non-factor graph except possibly G_{n,k} itself, which the paper asserts has no k-factor; this last assertion is what makes the bound sharp.

Load-bearing premise

The sharpness of the bound rests on the claim that the extremal graph G_{n,k} has no k-factor; the paper's proof of that claim counts only edges leaving the middle clique and misses that K_{k+1} itself is already k-regular.

Editorial extensions

If this is right

For every k ≥ 2, a single number ρ(G_{n,k}) decides k-factor existence for all large graphs with minimum degree at least k: if the spectral radius is at least that number, a k-factor is guaranteed.
The theorem solves the non-bipartite case of the binding-number problem for every k ≥ 2, since G_{n,k} is 1-binding.
The structural conclusion is rigid: any graph that reaches the threshold and still lacks a k-factor would have to be isomorphic to G_{n,k}.
The threshold is claimed to be best possible, because G_{n,k} itself is asserted to contain no k-factor; if that assertion holds, no smaller constant can replace ρ(G_{n,k}).
The evenness condition kn ≡ 0 mod 2 is built into the statement, so the result also covers every k ≥ 2 for which a k-factor can exist at all.

Reading between the lines

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

The theorem's proof does not actually seem to need the extremal graph G_{n,k} to be factor-free; if G_{n,k} turns out to contain a k-factor, the sufficiency result would survive but the word 'sharp' would have to be withdrawn.
A concrete check for k = 2, n = 50 would settle the sharpness question immediately: K_3 is already a 2-factor on its own and the remaining large clique has a 2-factor, so an explicit 2-factor of G_{n,2} can likely be written down; that would contradict the paper's claimed sharpness.
The same obstruction-family-plus-spectral-maximization scheme could be adapted to [a,b]-factors or to odd factors, where the parity term in the f-factor theorem changes and may produce different extremal graphs.

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 headline: the main theorem is unsupported because the extremal graph G_{n,k} actually has a k-factor. The graph is K_k ∨ (K_{k+1} ∪ K_{n−1−2k}) plus k−1 edges from one vertex of K_{k+1}. The clique K_{k+1} is already k-regular, and the remaining k+(n−1−2k)=n−1−k vertices induce a complete graph K_{n−1−k}. That complete graph has a k-factor whenever k(n−1−k) is even; here kn even implies k(n−1−k)=kn−k(k+1) even, and n−1−k ≥ k+1 holds under the stated n bound. So a k-factor exists. The introduction's counting argument ignores that factor edges can stay inside K_{k+1}. This invalidates the claimed sharpness example, the membership checks in Lemmas 3.1 and 4.1, and the uniqueness conclusions that lean on them.

What is genuinely new: the problem is a natural spectral version of Fan–Lin's binding-number question for all k ≥ 2, and the proof architecture—use Tutte's f-factor theorem to force membership in a constrained graph class, then identify the spectrally extremal member—is reasonable. The edge-swapping argument in Lemma 3.1 is standard and may be repairable. Citations to the relevant spectral factor literature are appropriate. Conditional on a correct extremal graph, the approach could work.

Soft spots beyond the fatal one: equation (1) claims e(G) < (k+1)n − (k+1)^2, but G_{n,k} itself has roughly n^2/2 edges, so that inequality is false as written (likely e(\bar{G}) was meant). There is also an 's ≥ k' typo in Lemma 3.1. These are secondary next to the failure of the extremal construction.

Bottom line: this is a serious attempt at a legitimate problem, but the central example fails, so the theorem as stated is false. I would not cite it. If an editor wants a referee to document the counterexample, that is reasonable, but I would not expect the paper to survive in anything like its current form. A corrected version with a different no-k-factor extremal graph might deserve another look.

Referee Report

3 major / 3 minor

Summary. The paper investigates spectral radius conditions that force the existence of a k-factor in an n-vertex graph with minimum degree at least k. For k ≥ 2, kn even, and n ≥ max{k^2+6k+7, 20k+10}, the authors define an extremal graph G_{n,k} = K_k ∨ (K_{k+1} ∪ K_{n−1−2k}) with k−1 extra edges from one vertex of K_{k+1} to vertices of K_{n−1−2k}, assert that this graph has no k-factor, and prove Theorem 1.1: if ρ(G) ≥ ρ(G_{n,k}), then G has a k-factor unless G = G_{n,k}. The proof uses Tutte's f-factor theorem to translate the absence of a k-factor into membership in a class of graphs, then invokes spectral perturbation lemmas to identify the spectral extremal graph in that class.

Significance. A correct theorem of this type would be a meaningful contribution and would resolve Problem 1 of Fan and Lin for all k ≥ 2. The paper uses standard and appropriate tools — Tutte's f-factor theorem, the Hong–Shu–Fang spectral bound, Perron–Frobenius theory, and an edge-swap lemma — in a self-contained way, which is a strength. However, the central extremal construction is invalid: the asserted factor-free graph G_{n,k} in fact contains a k-factor. As a result, the claimed sharpness of the spectral bound and the uniqueness lemmas that support Theorem 1.1 are not established. The manuscript as it stands does not deliver its central claim.

major comments (3)

[Section 1, definition of G_{n,k}] The assertion that G_{n,k} contains no k-factor is false. The clique on V(K_{k+1}) is k-regular by itself, and the remaining n−k−1 vertices induce the complete graph K_{n−k−1}: the sets V(K_k) and V(K_{n−1−2k}) are internally complete and are joined to each other. Since k(n−k−1) = kn − k(k+1) is even (because kn is even and k(k+1) is even) and n−k−1 ≥ k+1 under the theorem's hypotheses, K_{n−k−1} has a k-factor. The union of that factor with E(K_{k+1}) is a k-factor of G_{n,k}. The counting argument in the introduction is incorrect because it ignores that each vertex of K_{k+1} already achieves degree k within that clique. Therefore G_{n,k} cannot serve as the sharpness example, and the exception in Theorem 1.1 is not a genuine exception.
[Section 3, Lemma 3.1] The claim 'Clearly, G_{n,k} ∈ G_k^n' is false. For B = V(K_{k+1}), each vertex in B has degree 2k inside G_{n,k} (k neighbors in K_{k+1} and k neighbors in K_k), except the one distinguished vertex that has k−1 additional edges to K_{n−1−2k}. Hence ∑_{u∈B} d_{G_{n,k}}(u) = (k+1)·2k + (k−1) = 2k^2 + 3k − 1, which exceeds the threshold k^2 + 2k − 1 in the definition of G_k^n. Consequently Lemma 3.1 does not apply to G_{n,k}, and its conclusion cannot identify G_{n,k} as the extremal graph in G_k^n.
[Section 4, Lemma 4.1] The assertion 'It is easy to check that G_{n,k} ∈ G_n,k' is false. Taking S = V(K_k) and T = V(K_{k+1}), the left-hand side of the defining inequality is ∑_{u∈T} d_{G−S}(u) = k(k+1) + (k−1) = k^2 + 2k − 1, while the right-hand side is k|T| − k|S| − 2 + q = k(k+1) − k^2 − 2 + 1 = k − 1. For k ≥ 2, the inequality fails. Thus G_{n,k} is not a member of the class G_n,k, and the final step of Theorem 1.1's proof, which concludes G = G_{n,k} from Lemma 4.1, does not go through. The proof of Theorem 1.1 is therefore unsupported.

minor comments (3)

[Title] The title reads 'Spectral conditions for graphs to containk-factors'; there should be a space before 'k-factors'.
[Section 4, Subcase 1.2] In the displayed chain after inequality (3), the expression 't(n−t)t' appears to be a typo; it should presumably be 't(n−t)'.
[Throughout] The notation is inconsistent: the extremal graph is usually G_{n,k}, but the class of graphs in Section 4 is also denoted G_n,k. This makes statements such as 'G_{n,k} ∈ G_n,k' harder to read and should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof derives the spectral condition from independent external lemmas; the sharpness claim about G_{n,k} is a correctness defect, not a circular one.

full rationale

The derivation chain is not circular. The proof of Theorem 1.1 assumes the negation of the conclusion (no k-factor) and uses Tutte's f-factor theorem (Lemma 2.4, cited from [11]) to obtain the structural condition defining Gn,k. Lemma 4.1 then independently maximizes spectral radius over that class via the Hong-Shu-Fang bound (Lemma 2.3, cited from [7]), Perron-Frobenius arguments, and the edge-replacement lemma (Lemma 2.2, cited from [13]). Nothing in these steps assumes the target theorem or the no-k-factor status of G_{n,k}; the target result is not used as an input anywhere. The introduction's separate assertion that G_{n,k} contains no k-factor is used only to advertise sharpness, not to derive the inequality; even if that assertion is false, that is a correctness defect, not circularity. The only self-citation is Lemma 2.2 from [13] by the corresponding author, but it is a standard spectral perturbation lemma with independent content, used as a tool, and it does not encode the target result. There are no fitted inputs renamed as predictions and no uniqueness theorem imported from the authors' prior work.

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

No free parameters are fitted and no new entities are postulated. The main premises are standard graph theory theorems; the fatal issue is not an axiom but the incorrect verification that G_{n,k} is k-factor-free and belongs to \mathcal{G}_{n,k}.

assumptions (5)

standard math Tutte's f-factor theorem (Lemma 2.4) characterizes existence of k-factors via the inequality for all disjoint vertex sets S and T.
Used in the proof of Theorem 1.1 to translate the absence of a k-factor into membership in the set \mathcal{G}_{n,k}.
standard math Hong-Shu-Fang bound (Lemma 2.3) upper-bounds spectral radius in terms of edge count and minimum degree.
Used to derive the complement edge bound (1) in Lemma 4.1, though the text misstates the bound as concerning e(G).
standard math Perron-Frobenius theorem gives a positive eigenvector for connected graphs.
Used throughout the Perron vector comparisons in Lemma 3.1 and Lemma 4.1.
standard math Edge-swap lemma (Lemma 2.2) from reference [13] states that moving an edge toward a larger Perron coordinate increases spectral radius.
Used to force structural properties of extremal graphs; the lemma comes from a prior paper by the corresponding author but is an external published result.
domain assumption The domain assumptions n >= max{k^2+6k+7, 20k+10} and kn even.
These inequalities and parity are stated in Theorem 1.1 and are used in algebraic estimates and for existence of k-factors on complete graphs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Spectral conditions for graphs to contain $k$-factors." pith.science (2026). https://pith.science/paper/7UVWZJBB

@misc{pith2026250805678,
  author       = {Pith},
  title        = {Pith review of: Spectral conditions for graphs to contain $k$-factors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7UVWZJBB}},
  note         = {Machine review of arXiv:2508.05678}
}

abstract

Let $G$ be a graph. The spectral radius $\rho(G)$ of $G$ is the largest eigenvalue of its adjacency matrix. For an integer $k\geq1$, a $k$-factor of $G$ is a $k$-regular spanning subgraph of $G$. Assume that $k$ and $n$ are integers satisfying $k\geq2,kn\equiv0~(\mod2)$ and $n\geq\max\left\{k^{2}+6k+7,20k+10\right\}$. Let $G$ be a graph of order $n$ and with minimum degree at least $k$. In this paper, we give a sharp lower bound of $\rho(G)$ to guarantee that $G$ contains a $k$-factor.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A note on the spectral radius and $[a,b]$-factor of graphs
math.SP 2025-08 conditional novelty 6.0 of 10

For b > a, every connected n-vertex graph with minimum degree at least a and spectral radius at least rho(H^{a,b}_n) contains an [a,b]-factor, except H^{a,b}_n itself.

Reference graph

Works this paper leans on

13 extracted references · 11 canonical work pages · cited by 1 Pith paper

[1]

Brouwer and W

A. Brouwer and W. Haemers, Spectra of Graphs, Springer 2012

2012
[2]

Cho, J.Y

E.-K. Cho, J.Y. Hyun, S. O and J.R. Park, Sharp conditions for the existence of an even [a, b]-factor in a graph, Bull. Korean Math. Soc. 58 (1) (2021) 31-46

work page 2021
[3]

Y. Chen, D. Fan and H. Lin, Factors, spectral radius and toughness in bipartite graphs, Discrete Appl. Math. 355 (2024) 223-231

work page 2024
[4]

Fan and H

D. Fan and H. Lin, Binding number, k-factor and spectral radius of graphs, Electron. J. Comb. 31 (1) (2024) P1.30

work page 2024
[5]

Spectral conditions for $k$-extendability and $k$-factors of bipartite graphs

D. Fan and H. Lin, Spectral conditions for k-extendability and k-factors of bipartite graphs, arXiv:2211.09304

work page Pith review arXiv
[6]

D. Fan, H. Lin and H. Lu, Spectral radius and [ a, b]-factors in graphs, Discrete Math. 345 (7) (2022) 112892

work page 2022
[7]

Hong, J.L

Y. Hong, J.L. Shu and K.F. Fang, A sharp upper bound of the spectral radius of graphs, J. Comb. Theory, Ser. B 81 (2001) 177-183

work page 2001
[8]

Hao and S

Y. Hao and S. Li, Tur´ an-type problems on [a, b]-factors of graphs, and beyond, Elec- tron. J. Comb. 31 (3) (2024) P3.23

work page 2024

Show all 13 references

[9]

Y. Hao, S. Li and Y. Yu, Bipartite binding number, k-factor and spectral radius of bipartite graphs, Discrete Math. 348 (2025) 114511

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

2021
[11]

Tutte, The factors of graphs, Canad

W.T. Tutte, The factors of graphs, Canad. J. Math. 4 (1952) 314-328. 13

1952
[12]

Wei and S

J. Wei and S. Zhang, Proof of a conjecture on the spectral radius condition for [ a, b]- factors, Discrete Math. 346 (3) (2023) 113269

2023
[13]

Zhang, The spectral radius and k-power of Hamilton cycle of graphs, Discrete Math

W. Zhang, The spectral radius and k-power of Hamilton cycle of graphs, Discrete Math. 347 (2024) 113983. 14

2024

Pith tools

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

[1] [1]

Brouwer and W

A. Brouwer and W. Haemers, Spectra of Graphs, Springer 2012

2012

[2] [2]

Cho, J.Y

E.-K. Cho, J.Y. Hyun, S. O and J.R. Park, Sharp conditions for the existence of an even [a, b]-factor in a graph, Bull. Korean Math. Soc. 58 (1) (2021) 31-46

work page 2021

[3] [3]

Y. Chen, D. Fan and H. Lin, Factors, spectral radius and toughness in bipartite graphs, Discrete Appl. Math. 355 (2024) 223-231

work page 2024

[4] [4]

Fan and H

D. Fan and H. Lin, Binding number, k-factor and spectral radius of graphs, Electron. J. Comb. 31 (1) (2024) P1.30

work page 2024

[5] [5]

Spectral conditions for $k$-extendability and $k$-factors of bipartite graphs

D. Fan and H. Lin, Spectral conditions for k-extendability and k-factors of bipartite graphs, arXiv:2211.09304

work page Pith review arXiv

[6] [6]

D. Fan, H. Lin and H. Lu, Spectral radius and [ a, b]-factors in graphs, Discrete Math. 345 (7) (2022) 112892

work page 2022

[7] [7]

Hong, J.L

Y. Hong, J.L. Shu and K.F. Fang, A sharp upper bound of the spectral radius of graphs, J. Comb. Theory, Ser. B 81 (2001) 177-183

work page 2001

[8] [8]

Hao and S

Y. Hao and S. Li, Tur´ an-type problems on [a, b]-factors of graphs, and beyond, Elec- tron. J. Comb. 31 (3) (2024) P3.23

work page 2024