A Fan-type condition involving bipartite independence number for hamiltonicity in graphs

Hongxi Liu; Long-tu Yuan; Xiaowen Zhang

REVIEW 2 major objections 4 minor 1 cited by

A Fan-type condition involving bipartite independence number for hamiltonicity in graphs

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 a 2-connected graph whose nonadjacent pairs at distance two have max degree at least its bipartite independence number is hamiltonian, and that the 3-connected analogue with threshold increased by one is…

desk verdict A credible Fan-type generalization to bipartite independence number, but the proof of Theorem 1.5 hinges on an under-proved Claim 3.1 that a referee should push hard on. read the letter →

arxiv 2506.02687 v3 pith:J545AMYM submitted 2025-06-03 math.CO

Hongxi Liu , Long-Tu Yuan , Xiaowen Zhang This is my paper

classification math.CO MSC 05C4505C38

keywords Hamiltonianhamiltonian-connectedFan-typeconditionbipartiteindependencenumberdegreedistancetwo2-connectedgraphs3-connected

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 aims to establish that a single degree bound — the maximum of the two endpoint degrees, checked only at pairs of nonadjacent vertices at distance two — controls hamiltonicity. The main claims are that a 2-connected graph of order at least three is hamiltonian whenever every such pair satisfies $\max\{d_G(x), d_G(y)\} \ge \widetilde{\alpha}(G)$, and that a 3-connected graph is hamiltonian-connected whenever the threshold is $\widetilde{\alpha}(G)+1$, where $\widetilde{\alpha}(G)$ is the bipartite independence number. These results would unify the classical minimum-degree, degree-sum, and distance-two max-degree approaches under one parameter, and they generalise the recent degree-sum theorems proved for the same parameter. A sympathetic reader should care because the threshold is often much smaller than the order of the graph, so the condition is genuinely weaker than the classical $n/2$ or $n$ bounds.

What carries the argument

The load-bearing object is the bipartite independence number $\widetilde{\alpha}(G)$, defined as the smallest $q$ for which there exist positive integers $s,t$ with $s+t=q+1$ such that every pair of disjoint vertex sets $A,B$ with $|A|=s$ and $|B|=t$ has at least one edge between them. It measures how hard it is to find two large vertex sets with no cross edge, and the proofs use it as a counting device: after choosing $s$ neighbours of one endpoint on a longest path, the condition $\widetilde{\alpha}(G)=s+t-1$ forces an edge between the shifted neighbour sets, which in turn either extends the path or closes a Hamilton cycle. For Theorem 1.5 the additional machinery is a maximal counterexample $G$, the set $V^*$ of vertices of degree at least $\widetilde{\alpha}(G)+1$, the structural Claim 3.1 asserting that $G[V^*]$ is not a clique, and a Hamilton path in $G+e$ whose rotations and reversals produce the required contradictory paths.

What would settle it

A concrete way to settle Theorem 1.5 is to exhaustively test all 3-connected graphs of small order, checking the distance-two condition $\max\{d_G(x),d_G(y)\} \ge \widetilde{\alpha}(G)+1$ and testing hamiltonian-connectedness; any graph satisfying the condition without a Hamilton path between some pair refutes the theorem. A more targeted check is to examine the auxiliary clique-matching graphs described in Claim 3.1 and verify or refute their hamiltonian-connectedness directly.

Watch

Extended reading notes

Core claim

The paper's central claim is that the bipartite independence number $\widetilde{\alpha}(G)$ — the smallest integer $q$ for which some $s+t=q+1$ forces an edge between every pair of disjoint subsets of sizes $s$ and $t$ — is exactly the right threshold for a distance-two max-degree condition. Theorem 1.4 asserts that in a 2-connected graph, $\max\{d_G(x), d_G(y)\} \ge \widetilde{\alpha}(G)$ on every nonedge at distance two forces a Hamilton cycle; Theorem 1.5 asserts that in a 3-connected graph the same condition with threshold $\widetilde{\alpha}(G)+1$ forces a Hamilton path between every two vertices. The proofs proceed by taking a longest path, partitioning the neighbours of its endpoints into four sets around a chosen cut, and using the definition of $\widetilde{\alpha}(G)$ to force an edge between shifted neighbourhoods; any such edge produces a longer path or a Hamilton cycle, and the counting then contradicts the degree assumptions. The paper also supplies three extremal examples showing that both thresholds are tight and that 3-connectivity in Theorem 1.5 cannot be dropped.

Load-bearing premise

The load-bearing premise is that every 3-connected graph assembled from cliques and matchings in the subcases of Claim 3.1 is hamiltonian-connected; the text asserts this with 'it is easy to see' and 'with the same argument' rather than proving it in detail, and if any such auxiliary graph failed to be hamiltonian-connected, the maximal-counterexample argument for Theorem 1.5 would lose its starting point.

Editorial extensions

If this is right

If Theorem 1.4 is correct, every 2-connected graph whose nonadjacent pairs at distance two have $\max\{d_G(x),d_G(y)\} \ge \widetilde{\alpha}(G)$ contains a Hamilton cycle, so the bipartite independence number becomes a usable sufficient-condition parameter for hamiltonicity.
If Theorem 1.5 is correct, every 3-connected graph with the distance-two condition at threshold $\widetilde{\alpha}(G)+1$ has a Hamilton path between any two prescribed vertices, a property stronger than hamiltonicity.
The extremal examples $K_n \vee K_{n+1}$ and $K_n \vee K_n$ show that neither threshold can be lowered, and the example $(K_{a-2} \cup K_1) \vee K_2$ shows that 3-connectivity is necessary in Theorem 1.5.
Because $\max\{d_G(x),d_G(y)\} \ge \widetilde{\alpha}(G)$ implies $d_G(x)+d_G(y) \ge 2\widetilde{\alpha}(G)$, Theorem 1.4 generalises the degree-sum theorem for hamiltonicity, and Theorem 1.5 likewise generalises the corresponding hamiltonian-connected result.

Reading between the lines

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

The subcase analysis in Claim 3.1 is where the proof of Theorem 1.5 is least explicit: several 3-connected auxiliary graphs are declared hamiltonian-connected with 'it is easy to see' or 'with the same argument.' A reader who wants certainty about Theorem 1.5 should expand these checks before relying on the result.
The same parameter might serve as a threshold for other spanning structures, such as vertex-pancyclicity or the existence of spanning trees with bounded degree, following the pattern that already connects minimum degree, bipartite independence number, and hamiltonian properties.
The maximal-counterexample method with an added edge suggests a testable question: determine whether the threshold in Theorem 1.5 can be varied when the high-degree set $V^*$ is guaranteed not to be a clique, or whether extra structural hypotheses on $G-V^*$ would allow a lower 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

Worth a look if you work on degree conditions for hamiltonicity. This paper proves Fan-type max-degree conditions involving the bipartite independence number: Theorem 1.4 gives a hamiltonicity condition with threshold ~alpha(G), and Theorem 1.5 gives hamiltonian-connectivity with threshold ~alpha(G)+1. Those are natural generalizations of the recent Ore-type results by Li and Liu, and the bounds look tight (modulo the typos below). The main line of proof is standard longest-path rotation, and the counting arguments in Claim 2.1 and Claims 3.3-3.6 are recognizably correct; I did not find a hidden edge case in the rotation cases.

The real soft spot is Claim 3.1 in the proof of Theorem 1.5. To show V* cannot be a clique, the authors assert that the structured graphs built from cliques and a 3-matching are hamiltonian-connected, with 'it is easy to see' / 'with the same argument'. That is load-bearing: if those graphs are not always hamiltonian-connected, the maximal-counterexample argument has no starting nonedge uv. The stress-test example with two triangles joined by a perfect matching does not actually satisfy the admissible degree setup, so I don't think the claim is false, but the proof as written does not use the degree separation between V* and G-V* explicitly, and that separation is essential. A referee should ask for a complete proof of this structural hamiltonian-connectedness.

Other issues are presentation-level but real: in Theorem 1.4's proof, s and t are used before the definition is invoked; in Theorem 1.5, the added edge e is described as being in E(G) when it should be a nonedge; and the tightness examples are mistyped (Kn ∨ Kn+1 is complete, so it is not a counterexample to hamiltonicity; likely an independent set was intended, and similarly for G2). These are fixable.

Bottom line: the theorems are new, the core proof is mostly sound, and the paper deserves serious refereeing, but it is not ready to accept as written. The authors should be asked to expand Claim 3.1 and clean up the typos. I'd bring it to a reading group if the group likes hamiltonicity results, mainly to see whether the structural hamiltonian-connectivity lemma actually goes through without extra assumptions.

Referee Report

2 major / 4 minor

Summary. The paper proves two Fan-type degree conditions involving the bipartite independence number \tilde{\alpha}(G). Theorem 1.4 states that every 2-connected graph of order at least three satisfying max{d(x),d(y)} \ge \tilde{\alpha}(G) for every nonadjacent pair at distance two is hamiltonian. Theorem 1.5 states that every 3-connected graph satisfying the analogous inequality with threshold \tilde{\alpha}(G)+1 is hamiltonian-connected. The authors also give examples intended to show that both thresholds are tight and that 3-connectivity is necessary in Theorem 1.5.

Significance. If the proofs can be completed, Theorems 1.4 and 1.5 are natural Fan-type analogues of the recent Ore-type results of Li and Liu, and the claimed thresholds are tight. The paper is self-contained, does not rely on prior results of the authors, and the rotation arguments in the two cases of Theorem 1.5 are mostly standard and checkable. The main weakness is concentrated in Claim 3.1, whose abbreviated proof carries the entire weight of the maximal-counterexample setup for Theorem 1.5.

major comments (2)

[Section 3, Claim 3.1] The proof of Claim 3.1 is the pivot of Theorem 1.5, but its key hamiltonian-connectedness assertions are not proved. After reducing to the case where G[V*] and every component of G-V* is a clique, the text asserts "it is easy to see" (in the cases m=1 and m>=2 with |V(D_i)|>=3) and "with the same argument" (in the case of a small component) that G is hamiltonian-connected. This is load-bearing: Claim 3.1 is the only reason the proof may select a nonedge uv inside V*, which is then needed for Claim 3.2 and for the subsequent rotation arguments. The assertion is not automatic for 3-connected graphs built from cliques and matchings, and the proof does not explicitly use the degree separation between V* and G-V* in these cases. Please replace this passage with a complete proof, or a separate lemma, exhibiting Hamilton paths between all pairs of vertices in the stated configurations.
[Section 3, Claim 3.1, m>=2] The claim that for |V(D_i)|>=3 there exists a matching of cardinality three between V(D_i) and V* is not justified by 3-connectivity alone. Three-connectivity gives |N_{V*}(V(D_i))|>=3, but obtaining three vertex-disjoint edges requires a Hall-type argument; without using that G[V*] and D_i are cliques, and that V* separates the components, the stated matching need not exist. Please supply the missing argument or state and prove the auxiliary lemma.

minor comments (4)

[Section 2, proof of Theorem 1.4] The counting argument after Claim 2.1 uses integers s and t before they are defined; the proof should state explicitly that s,t are chosen with s<=t and s+t=\tilde{\alpha}(G)+1.
[Section 3, proof of Theorem 1.5] In the paragraph defining r, the path P has vertices v1,...,vn, but the text writes "1<=r<=m"; this should be "1<=r<=n".
[Section 1, tightness examples] As printed, G1=K_n\vee K_{n+1} and G2=K_n\vee K_n are complete graphs and hence hamiltonian (respectively hamiltonian-connected), so they do not illustrate the claimed sharpness. The authors presumably mean K_n\vee \overline{K_{n+1}} and K_n\vee \overline{K_n}; please correct the notation.
[Section 3, Claim 3.2] The admissibility check in G+e should distinguish paths of length two that use e from those that do not; as written, only the former case is described, although the latter follows from admissibility of G and monotonicity of degrees.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proofs are self-contained and the bipartite independence number is used only through its defining property.

full rationale

The paper derives Theorems 1.4 and 1.5 by direct longest-path and maximal-counterexample arguments. The bipartite independence number eα(G) enters the proofs exclusively through its definition: whenever s+t = eα(G)+1, any two disjoint sets A and B with |A|=s and |B|=t must have an edge between them. This is an application of the defining property, not an assumption of the target theorem, and no parameter is fitted to data or renamed as a prediction. The paper does not rely on any load-bearing self-citation: prior results by Li and Liu, McDiarmid and Yolov, and Zhou et al. are cited only as background, while the proofs of Theorems 1.4 and 1.5 are carried out from the stated degree condition and the definition of eα. The abbreviated structural assertions inside Claim 3.1, such as 'it is easy to see that G is hamiltonian-connected', are potential correctness gaps rather than circular steps: they do not invoke the theorem being proved, and a failure there would be a false lemma, not a derivation that reduces to its own input. Therefore no specific circular reduction can be exhibited, and the honest finding is no significant circularity.

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

The central claim rests only on standard graph theory facts and the definition of bipartite independence number. No free parameters are fitted and no new entities are introduced. The main unstated support is the matching lemma for k-connected graphs and the longest-path rotation framework.

assumptions (4)

standard math Matching lemma: in a k-connected graph, any two disjoint vertex sets of size at least k have a matching of size k.
Used in Claim 3.1 to produce matchings of size three between components of G-V* and V*.
standard math Longest-path endpoint property: in a longest path, all neighbors of the endpoints lie on the path; otherwise the path could be extended.
Used throughout the proofs to restrict neighbor sets to the path.
standard math Adding edges cannot increase the bipartite independence number.
Used in Claim 3.2 to lift admissibility from G to G+e.
standard math Finite simple graph setting and standard definitions of hamiltonian and hamiltonian-connected.
Background for the theorems.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Fan-type condition involving bipartite independence number for hamiltonicity in graphs." pith.science (2026). https://pith.science/paper/J545AMYM

@misc{pith2026250602687,
  author       = {Pith},
  title        = {Pith review of: A Fan-type condition involving bipartite independence number for hamiltonicity in graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J545AMYM}},
  note         = {Machine review of arXiv:2506.02687}
}

abstract

The bipartite independence number of a graph $G$, denoted by $\widetilde{\alpha}(G)$, is defined as the smallest integer $q$ for which there exist positive integers $s$ and $t$ with $s + t = q + 1$, such that for any two disjoint subsets $A, B \subseteq V(G)$ with $|A| = s$ and $|B| = t$, there exists an edge between $A$ and $B$. In this paper, we prove that for a 2-connected graph $G$ of order at least three, if $\max\{d_G(x), d_G(y)\} \ge \widetilde{\alpha}(G)$ for every pair of nonadjacent vertices $x, y$ at distance two, then $G$ is hamiltonian. Moreover, we prove that if $G$ is 3-connected and $\max\{d_G(x), d_G(y)\} \ge \widetilde{\alpha}(G)+1$ for every pair of nonadjacent vertices $x, y$ at distance two, then $G$ is hamiltonian-connected. Our results generalize the recent work by Li and Liu.

Figures

Figures reproduced from arXiv: 2506.02687 by the authors.

**Figure 2.** Illustration of the configurations in Case 2. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Sign in 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

Cycles and paths through vertices whose degrees are at least the bipartite-hole-number
math.CO 2025-06 reject novelty 4.0 of 10

Every 2-connected graph has a cycle through all vertices of degree at least its bipartite-hole-number, and high-degree pairs are joined by a path through all such vertices.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages · cited by 1 Pith paper

[1]

Bondy and U.S.R

J.A. Bondy and U.S.R. Murty, Graph theory. Graduate texts in mathematics, vol. 244, Springer, 2008

work page 2008
[2]

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
[3]

Chv´ atal and P

V. Chv´ atal and P. Erd˝ os, A note on hamiltonian circuits,Discrete Math., 2 (1972) 111–113

work page 1972
[4]

Dirac, Some theorems on abstract graphs, Proc

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

work page 1952
[5]

Dragani´ c, D.M

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

work page 2024
[6]

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. 11

work page 1984
[7]

Faudree, R.J

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

work page 1989
[8]

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

work page 2014

Show all 16 references

[9]

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

2024
[10]

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
[11]

Li and F

C. Li and F. Liu, An Ore-type condition for hamiltonicity in graphs, (2025) arXiv: 2504.04493

2025 arXiv
[12]

McDiarmid and N

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

2017
[13]

Ore, Note on Hamilton circuits, Amer

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

1960
[14]

Ore, Hamilton connected graphs, J

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

1963
[15]

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

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

1996
[16]

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. 12

2024

Pith tools

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

[1] [1]

Bondy and U.S.R

J.A. Bondy and U.S.R. Murty, Graph theory. Graduate texts in mathematics, vol. 244, Springer, 2008

work page 2008

[2] [2]

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

[3] [3]

Chv´ atal and P

V. Chv´ atal and P. Erd˝ os, A note on hamiltonian circuits,Discrete Math., 2 (1972) 111–113

work page 1972

[4] [4]

Dirac, Some theorems on abstract graphs, Proc

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

work page 1952

[5] [5]

Dragani´ c, D.M

N. Dragani´ c, 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]

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. 11

work page 1984

[7] [7]

Faudree, R.J

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

work page 1989

[8] [8]

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

work page 2014