Cycles and paths through vertices whose degrees are at least the bipartite-hole-number

Chengli Li; Feng Liu; Yurui Tang

REVIEW 2 major objections 4 minor 1 cited by

Cycles and paths through vertices whose degrees are at least the bipartite-hole-number

T0 review · 2 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 This paper proves that in every 2-connected graph a single cycle contains all vertices of degree at least the bipartite-hole-number $\widetilde{\alpha}(G)$, and that any two vertices of degree at least $\widetilde{\alpha}(G)+1$ are joined…

desk verdict The cycle theorem (1.4) looks solid and is a real generalization, but the path theorem (1.8) has a load-bearing gap in Claim 2 that needs repair before the paper is acceptable. read the letter →

arxiv 2506.09750 v1 pith:3GJRODEA submitted 2025-06-11 math.CO

Chengli Li , Feng Liu , Yurui Tang This is my paper · ORCID

classification math.CO MSC 05C4505C38

keywords bipartite-hole-numberHamiltoniancycleHamiltonian-connecteddegreethresholdthroughspecifiedvertices2-connectedgraphcommonneighborhoodsindependencenumber

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

The paper proves two degree-threshold theorems in which the cutoff is the bipartite-hole-number $\widetilde{\alpha}(G)$, not the order $n$ of the graph. Theorem 1.4 states that every 2-connected graph contains a cycle passing through all vertices of degree at least $\widetilde{\alpha}(G)$. Theorem 1.8 states that in any connected graph, for any two vertices $u,v$ of degree at least $\widetilde{\alpha}(G)+1$, there is a $(u,v)$-path containing every vertex of degree at least $\widetilde{\alpha}(G)+1$. Because $\widetilde{\alpha}(G) \le \lceil n/2 \rceil$, these statements are stronger than the classical $n/2$ cycle theorem and the $\widetilde{\alpha}(G)+1$ hamiltonian-connectedness theorem that inspired them; Section 3 adds a Hamiltonicity criterion based on common neighborhoods of vertices at distance two.

What carries the argument

The machinery is the bipartite-hole-number $\widetilde{\alpha}(G)$, together with an extremal-cycle and extremal-path argument that uses the absence of an $(s,t)$-bipartite-hole to bound the size of mutually non-adjacent neighborhood sets. In the proofs, a longest cycle or a $(u,v)$-path maximizing the number of high-degree vertices is chosen; neighborhood sets are split into segments along that structure, and whenever two such sets have no edges between them, the no-hole property forces one of them to have size below its threshold. This forces an edge that creates a detour containing every high-degree vertex, contradicting the extremal choice.

What would settle it

Check the exact step in Claim 1 of Theorem 1.8 where $N_{Q^*}(v_q)=\emptyset$ is asserted; a small connected graph in which a shortest $(w,V(P))$-path has an internal vertex adjacent to $v_q$ while $P$ still maximizes the number of high-degree vertices would invalidate that claim. Separately, a computer search over all 2-connected graphs with up to ten vertices for one whose vertices of degree at least $\widetilde{\alpha}(G)$ do not all lie on a common cycle would refute Theorem 1.4 itself.

Watch

Extended reading notes

Core claim

The central claim is that the bipartite-hole-number acts as a degree threshold for forcing a cycle or path through all sufficiently high-degree vertices. An $(s,t)$-bipartite-hole is a pair of disjoint vertex sets $A,B$ with $|A|=s$, $|B|=t$ and no edge between them; $\widetilde{\alpha}(G)$ is the least $k$ such that some split $s+t=k+1$ forbids every such hole. The paper shows that a 2-connected graph has one cycle containing every vertex with degree at least $\widetilde{\alpha}(G)$, and that any two vertices of degree at least $\widetilde{\alpha}(G)+1$ are joined by a path containing every vertex of degree at least $\widetilde{\alpha}(G)+1$. These results extend the $n/2$ cycle theorem and the $\widetilde{\alpha}(G)+1$ hamiltonian-connectedness theorem, and the application in Section 3 derives a sufficient condition for Hamiltonicity from a common-neighborhood inequality at distance two.

Load-bearing premise

In the proof of Theorem 1.8, the load-bearing step is the unproved assertion that, with the path chosen to maximize the number of high-degree vertices and the attachment path chosen shortest, no internal vertex of the attachment path is adjacent to the next high-degree vertex on the chosen path; the extremal choice alone does not obviously forbid such an adjacency.

Editorial extensions

If this is right

Every 2-connected graph with $\delta(G) \ge \widetilde{\alpha}(G)$ is hamiltonian, since the guaranteed cycle then contains all vertices.
Every connected graph with $\delta(G) \ge \widetilde{\alpha}(G)+1$ is hamiltonian-connected, since any two vertices can be joined by a path through all vertices.
The classical $n/2$ cycle theorem is a special case, because $\widetilde{\alpha}(G) \le \lceil n/2\rceil$.
The previously known minimum-degree $\widetilde{\alpha}(G)+1$ hamiltonian-connectedness theorem is a special case of Theorem 1.8.
Theorem 3.1 yields Hamiltonicity of any 2-connected graph in which every distance-two pair of low-degree vertices has enough common neighbors.

Reading between the lines

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

Because $\widetilde{\alpha}(G)$ can be much smaller than $n/2$ in dense or structured graphs, the theorems replace a global order-based threshold with a local hole-based one; a natural next step is to test whether the same replacement works for vertex-pancyclicity or for paths through prescribed vertex sets.
The proof of Theorem 1.8 depends on a maximality claim about internal vertices of the attachment path; checking that claim on small examples is the fastest way to see whether the argument needs repair, even if the theorem itself survives.
One could attempt to strengthen Theorem 1.4 by replacing 'cycle' with 'cycle of prescribed length' or by relaxing 2-connectedness to a weaker connectivity condition, using $\widetilde{\alpha}(G)$ as the threshold.

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

Two things to know. The paper's main cycle theorem (1.4) — every 2-connected graph has a cycle through all vertices of degree at least the bipartite-hole-number — looks correct and genuinely extends Bollobás-Brightwell/Shi and McDiarmid-Yolov. The path version (1.8) is attractive, but its proof has a real gap that makes the paper unacceptable as written.

The novelty is moderate but legitimate. The authors replace the n/2 threshold with ~α(G) and adapt the known path-switching framework. The proof of 1.4 is careful and held up under checking; the application to a Fan-type condition (Theorem 3.1) also follows the same template and works.

The problem is in the proof of 1.8, Claim 2. The argument assumes |NR(w)| ≥ t and then applies the no-(s,t)-bipartite-hole condition to the set NR[w] \ V(Q). But if Q has length at least 2, that set has only |NR(w)| − 1 ≥ t − 1 vertices, not t. The no-hole condition requires sets of size exactly s and t, so the contradiction does not follow. This is load-bearing: it is the only mechanism producing the contradiction in Claim 2. The gap looks repairable — a t-subset of NR(w) with a separate argument for the neighbor on Q should do it — but it is not a cosmetic slip.

The reader's additional worry about Claim 1 is less serious; the stress-test note's repair (replacing a segment of Q to get a shorter path) works. There is also a minor flaw in the proof of 1.4: the remark that a clique naturally contains a cycle fails for a clique of size two, but 2-connectivity rescues the claim. Trivial to fix.

Who is this for? Graph theorists working on Hamiltonian cycles and degree conditions. If the gap in 1.8 is fixed, the paper is a useful contribution and I would be happy to see it in print.

My recommendation: send it to peer review with a request for major revision. The main idea is sound, the gap is specific and probably fixable, and the theorems are worth having.

Referee Report

2 major / 4 minor

Summary. The paper studies sufficient conditions, expressed through the bipartite-hole-number $\widetilde{\alpha}(G)$, for the existence of cycles and paths through all vertices whose degrees are at least a prescribed threshold. Theorem 1.4 claims that every 2-connected graph contains a cycle through all vertices of degree at least $\widetilde{\alpha}(G)$. Theorem 1.8 claims that if two vertices $u,v$ have degree at least $\widetilde{\alpha}(G)+1$, then there is a $(u,v)$-path containing all vertices of degree at least $\widetilde{\alpha}(G)+1$. Section 3 derives a Hamiltonian sufficient condition, Theorem 3.1, from Theorem 1.4. The proofs are self-contained and rely on repeated applications of the absence of $(s,t)$-bipartite-holes together with path-switching constructions.

Significance. If the results are correct, they give genuine extensions of the Bollobás–Brightwell/Shi theorem and of the Zhou–Broersma–Wang–Lu result, replacing order-based or minimum-degree assumptions by a per-vertex threshold tied to $\widetilde{\alpha}(G)$. A strength of the manuscript is that the arguments are parameter-free, do not rely on fitted quantities, and are mostly explicit constructions. The claimed application in Theorem 3.1 is natural and would follow from Theorem 1.4. However, the proof of Theorem 1.8 currently contains a load-bearing counting gap in Claim 2, and Claim 1 of that proof is asserted rather than justified. These issues appear repairable within the scope of the paper, but the theorem is not fully established as written.

major comments (2)

[Section 2, Claim 2 (proof of Theorem 1.8)] After assuming $|N_R(w)| \ge t$, the proof invokes the absence of an $(s,t)$-bipartite-hole with the set $A = N_R[w] \setminus V(Q)$. When $Q$ has length at least two, $V(Q)$ contains both $w$ and the unique neighbor of $w$ on $Q$, so $|N_R[w] \setminus V(Q)| = |N_R(w)| - 1 \le t-1$. Thus the required set of size $t$ is not available, and the claimed edge between $A$ and $(N_P(v_q)^- \cup N_R(v_q)) \setminus \{v_p\}$ does not follow from the no-$(s,t)$-hole property. This step is load-bearing, since it is the only mechanism producing the contradiction in Claim 2. The gap appears repairable by taking a $t$-subset of $(N_R(w)\setminus V(Q)) \cup \{w\}$ and checking that the existing path constructions cover both $x=w$ and $x \in N_R(w)\setminus V(Q)$, but the proof as written is incomplete.
[Section 2, Claim 1 (proof of Theorem 1.8)] The assertion “by the choices of $P$ and $Q$, we have $N_{Q^*}(v_q)=\emptyset$” is stated without proof. It does not follow merely from the maximality of $P$, because a detour through an internal vertex of $Q$ may add no high-degree vertices and therefore may not contradict the choice of $P$. The statement can be justified by arguing that if such an internal vertex were adjacent to $v_q$, then either the resulting path has more high-degree vertices, or replacing $P$ by that path and $Q$ by its subpath ending at $w$ gives a shorter $(w,V(P))$-path, contradicting the joint choice of $P$ and $Q$. This argument should be included explicitly.

minor comments (4)

[Section 1, Theorem 1.8 statement] The theorem statement says “Let $G$ be a graph”, but the proof and the abstract assume $G$ is connected. As stated, the claim is false when $u$ and $v$ lie in different components; the connectedness hypothesis should be stated.
[Section 2, proof of Theorem 1.4, first paragraph] The sentence that the set of high-degree vertices “forms a clique, which naturally contains a cycle passing through all such vertices” is not literally true when that set has size one or two. The intended conclusion follows from 2-connectivity and the standard fact that every finite set of vertices in a 2-connected graph lies on a cycle, but this should be justified rather than asserted.
[Section 2, Case 2 of Theorem 1.8] In the displayed path for the case $y \in W_3^-$, the segment $y \rightarrow P[y,v_q]$ is written as a forward segment, but $y$ may lie after $v_q$ on $P$ when $y \in \{v_{q+1},\ldots,v_{k-1}\}$. This should be the reverse segment $\leftarrow P[y,v_q]$ for the path to be well-defined.
[Throughout] There are several minor typos and notational inconsistencies, including $r \in [2, , k-1]$ in Section 3, the undefined notation $s \in [t]$ (it should say $s \le t$), and inconsistent renderings of $\widetilde{\alpha}(G)$ as $e\alpha(G)$.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proofs are self-contained derivations from the bipartite-hole-number definition and standard path-switching arguments.

full rationale

The paper's central claims (Theorems 1.4 and 1.8) are proved by contradiction from the definition of the bipartite-hole-number eα(G) and elementary path surgery. The bipartite-hole-number is an extrinsic graph parameter defined independently of the target cycles/paths; the theorems do not assume the existence of the cycle/path they set out to prove. No parameter is fitted to data and then renamed as a prediction; there are no empirical inputs. The citations to Bollobás-Brightwell, Shi, McDiarmid-Yolov, Zhou et al. and Liu-Yuan-Zhang are used as motivational context or as prior results being generalized, and the derivations do not rely on any unpublished or same-author uniqueness theorem. The authors do not cite their own prior work in any load-bearing way; all cited results are due to other authors. Theorem 3.1 uses Theorem 1.4, but that is a legitimate application since Theorem 1.4 was proved independently in Section 2. The noted proof gap in Claim 2 of Theorem 1.8 concerning the size of the set used to apply the no-(s,t)-bipartite-hole condition is a correctness concern about the strength of a hypothesis, not a circularity concern, because the condition is not being used as an input equivalent to the conclusion. Therefore the derivation chain is self-contained and honest.

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

No free parameters are fitted and no new entities are postulated. The proofs rely on the standard definition of bipartite-hole-number and on routine graph-theoretic path manipulations; the only non-routine steps are the contested claims in Theorem 1.8.

assumptions (3)

domain assumption The bipartite-hole-number ~α(G) is finite and there exist positive integers s,t with s+t=~α(G)+1 such that G has no (s,t)-bipartite-hole.
Used throughout both proofs to apply the no-hole condition; this is the definition of the parameter, Section 1.
domain assumption The graph in Theorem 1.4 is 2-connected, and the graph in Theorem 1.8 is connected with endpoints of degree at least ~α(G)+1.
These are the hypotheses of the theorems; the proofs use 2-connectivity to ensure the counterexample structure and connectedness to obtain the auxiliary path Q.
standard math Standard path-switching and cycle-reversal operations on an oriented path produce simple cycles or paths containing prescribed vertices when the endpoint adjacencies hold.
The case analyses repeatedly build cycles by combining segments of P with chords; the validity of these constructions is implicit.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Cycles and paths through vertices whose degrees are at least the bipartite-hole-number." pith.science (2026). https://pith.science/paper/3GJRODEA

@misc{pith2026250609750,
  author       = {Pith},
  title        = {Pith review of: Cycles and paths through vertices whose degrees are at least the bipartite-hole-number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3GJRODEA}},
  note         = {Machine review of arXiv:2506.09750}
}

abstract

The bipartite-hole-number of a graph $G$, denoted by $\widetilde{\alpha}(G)$, is the minimum integer $k$ such that there exist positive integers $s$ and $t$ with $s + t = k + 1$, satisfying the property that for any two disjoint sets $A, B \subseteq V(G)$ with $|A| = s$ and $|B| = t$, there is at least one edge between $A$ and $B$. In 1992, Bollob\'as and Brightwell, and independently Shi, proved that every $2$-connected graph of order $n$ contains a cycle passing through all vertices whose degrees are at least $\frac{n}{2}$. Motivated by their result, we show that in any $2$-connected graph of order $n$, there exists a cycle containing all vertices whose degrees are at least $\widetilde{\alpha}(G)$. Moreover, we prove that for any pair of vertices in a connected graph $G$, if their degrees are at least $\widetilde{\alpha}(G) + 1$, then there exists a path joining them that contains all vertices whose degrees are at least $\widetilde{\alpha}(G) + 1$. The results extend two existing ones.

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

Edge-disjoint Hamilton cycles under a bipartite-hole condition
math.CO 2026-07 accept novelty 6.0 of 10

f(a,k), the min-degree threshold for k edge-disjoint Hamilton cycles under bipartite-hole number ≤ a, equals Θ(a + k + ak/log(k+2)).

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper

[1]

Bollobás and G

B. Bollobás and G. Brightwell, Cycles through specified vertices, Combinatorica, 13 (1993) 147–155

work page 1993
[2]

Bondy and U.S.R

J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Graduate Texts in Mathematics, vol. 244, 2008

work page 2008
[3]

Chen, Hamilton-connected, vertex-pancyclic and bipartite holes,Discrete Math.,345 (2022) 113158

M. Chen, Hamilton-connected, vertex-pancyclic and bipartite holes,Discrete Math.,345 (2022) 113158

work page 2022
[4]

Dirac, Some theorems on abstract graphs,Proc

G. Dirac, Some theorems on abstract graphs,Proc. London Math. Soc.(3) , 2 (1952) 69–81

work page 1952
[5]

Draganić, D.M

N. Draganić, D.M. Correia and B. Sudakov, A generalization of Bondy’s pancyclicity theorem, Comb. Prob. Comput. , 33 (2024) 554–563

work page 2024
[6]

Erdős, T

P. Erdős, T. Gallai, On maximal paths and circuits of graphs,Acta Math. Acad. Sci. Hungar. , 10 (1959) 337–356

work page 1959
[7]

Fan, New sufficient conditions for cycles in graphs,J

G. Fan, New sufficient conditions for cycles in graphs,J. Combin. Theory Ser. B , 37 (1984) 221–227

work page 1984
[8]

Faudree, R.J

R.J. Faudree, R.J. Gould, M.S. Jacobson and R.H. Schelp, Neighborhood unions and hamilto- nian properties in graphs,J. Combin. Theory Ser. B , 47 (1989) 1–9

work page 1989

Show all 18 references

[9]

Gould, Recent advances on the Hamiltonian problem: Survey III,Graphs Combin., 30 (2014) 1–46

R.J. Gould, Recent advances on the Hamiltonian problem: Survey III,Graphs Combin., 30 (2014) 1–46

2014
[10]

J. Han, J. Hu, L. Ping, G. Wang, Y. Wang and D. Yang, Spanning trees in graphs without large bipartite holes, Combin. Probab. Comput., 33 (2024) 270–285

2024
[11]

Li, Generalizations of Dirac’s theorem in Hamiltonian problem-A survey,Discrete Math., 313 (2013) 2034–2053

H. Li, Generalizations of Dirac’s theorem in Hamiltonian problem-A survey,Discrete Math., 313 (2013) 2034–2053

2013
[12]

H. Liu, L. Y and X. Zhang, A Fan-type condition involving bipartite independence number for hamiltonicity in graphs, (2025) arXiv:2506.02687. 10

2025 arXiv
[13]

McDiarmid and N

C. McDiarmid and N. Yolov, Hamilton cycles, minimum degree, and bipartite holes,J. Graph Theory, 86 (2017) 277–285

2017
[14]

Ore, Note on Hamilton circuits,Amer

O. Ore, Note on Hamilton circuits,Amer. Math. Monthly , 67 (1960) 55

1960
[15]

Ore, Hamilton connected graphs,J

O. Ore, Hamilton connected graphs,J. Math. Pures Appl. (9) , 42 (1963) 21–27

1963
[16]

Shi, 2-neighborhoods and hamiltonian conditions,J

R. Shi, 2-neighborhoods and hamiltonian conditions,J. Graph Theory, 16 (1992) 267–271

1992
[17]

West, Introduction to Graph Theory, Prentice Hall, Inc., 1996

D.B. West, Introduction to Graph Theory, Prentice Hall, Inc., 1996

1996
[18]

Q. Zhou, H. Broersma, L. Wang and Y. Lu, A note on minimum degree, bipartite holes, and hamiltonian properties, Discuss. Math. Graph Theory , 44 (2024) 717–726. 11

2024

Pith tools

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

[1] [1]

Bollobás and G

B. Bollobás and G. Brightwell, Cycles through specified vertices, Combinatorica, 13 (1993) 147–155

work page 1993

[2] [2]

Bondy and U.S.R

J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Graduate Texts in Mathematics, vol. 244, 2008

work page 2008

[3] [3]

Chen, Hamilton-connected, vertex-pancyclic and bipartite holes,Discrete Math.,345 (2022) 113158

M. Chen, Hamilton-connected, vertex-pancyclic and bipartite holes,Discrete Math.,345 (2022) 113158

work page 2022

[4] [4]

Dirac, Some theorems on abstract graphs,Proc

G. Dirac, Some theorems on abstract graphs,Proc. London Math. Soc.(3) , 2 (1952) 69–81

work page 1952

[5] [5]

Draganić, D.M

N. Draganić, D.M. Correia and B. Sudakov, A generalization of Bondy’s pancyclicity theorem, Comb. Prob. Comput. , 33 (2024) 554–563

work page 2024

[6] [6]

Erdős, T

P. Erdős, T. Gallai, On maximal paths and circuits of graphs,Acta Math. Acad. Sci. Hungar. , 10 (1959) 337–356

work page 1959

[7] [7]

Fan, New sufficient conditions for cycles in graphs,J

G. Fan, New sufficient conditions for cycles in graphs,J. Combin. Theory Ser. B , 37 (1984) 221–227

work page 1984

[8] [8]

Faudree, R.J

R.J. Faudree, R.J. Gould, M.S. Jacobson and R.H. Schelp, Neighborhood unions and hamilto- nian properties in graphs,J. Combin. Theory Ser. B , 47 (1989) 1–9

work page 1989