pith. sign in

arxiv: 2604.27535 · v1 · submitted 2026-04-30 · 🧮 math.CO

Pancyclicity in Graph Families with the Ore-Type Condition

Luyi Li , Yubo Wang , Guiying Yan This is my paper

Pith reviewed 2026-05-07 09:53 UTC · model grok-4.3

classification 🧮 math.CO
keywords rainbow cyclespancyclicityOre-type conditiongraph familyHamiltonian cycleBondy conjecturevertex pancyclicityextremal graph theory
0
0 comments X

The pith

Under the Ore-type condition, graph families have rainbow cycles of every length through each vertex unless all are the balanced bipartite graph.

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

This paper shows that if a family of n graphs on the same n vertices satisfies the Ore-type condition that the minimum degree sum of non-adjacent vertices across the family is at least n, then the family contains rainbow cycles of lengths 4 through n that cover every vertex. The sole exception occurs when every graph in the family is the complete bipartite graph with equal parts. This establishes rainbow pancyclicity and rainbow vertex-pancyclicity as corollaries, lending support to Bondy's meta-conjecture on the existence of cycles of all lengths in graphs with sufficient degree conditions, now in a multi-graph rainbow context.

Core claim

The central result is that for a family of n graphs on a common vertex set V with |V|=n satisfying σ(G) ≥ n, either every vertex in V is contained in a rainbow cycle of length ℓ for each ℓ from 4 to n, or all graphs in the family are equal to the complete bipartite graph K_{n/2, n/2}.

What carries the argument

The rainbow subgraph defined by an injection from edges to the family indices, combined with the Ore-type minimum degree-sum condition σ(G).

If this is right

  • The family is rainbow pancyclic.
  • The family is rainbow vertex-pancyclic.
  • The result is sharp due to the extremal family of balanced complete bipartite graphs.
  • It provides further evidence for Bondy's meta-conjecture in the rainbow setting.

Where Pith is reading between the lines

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

  • The condition may apply to other rainbow properties such as paths or trees.
  • Similar results could hold for families with fewer or more graphs than vertices.
  • Computational checks for small n could verify the absence of other extremal examples.

Load-bearing premise

The combinatorial analysis assumes that the balanced complete bipartite graphs are the only extremal configurations that meet the degree sum bound without the pancyclicity property.

What would settle it

Constructing or finding a family of n graphs on n vertices where the Ore-type condition holds but some vertex misses a rainbow cycle of a certain length between 4 and n, and the graphs are not all the balanced complete bipartite graph.

Figures

Figures reproduced from arXiv: 2604.27535 by Guiying Yan, Luyi Li, Yubo Wang.

Figure 1
Figure 1. Figure 1: The extremal graph Kt ∨ (K1 ∪ Km) 8, 9, 13, 19]. Inspired by the meta-conjecture and Theorem 1.3, we continue to consider the pancyclicity of the family of graphs under the Ore-type condition. In this paper, we prove the following result: Theorem 1.6. Let G = {G1, G2, ..., Gn} be a family of n-vertex graphs on the same vertex set V . If σ(G) ≥ n, then G is [4, n]-rainbow vertex-pancyclic or G1 = · · · = Gn… view at source ↗
Figure 2
Figure 2. Figure 2: The rainbow cycle of length n − 1 Claim 2.2. For any two distinct integers i, j ∈ [n], we have xixi+2 ∈/ E(Gj ). Proof. If xixi+2 ∈ E(Gj ) for some integer i ∈ [n − 1] and some j ∈ [n], then xixi+2 −→Cnxi is a rainbow cycle of length n − 1 containing x1, where xixi+2 ∈ E(Gj ) and xjxj+1 ∈ E(Gi) by Claim 2.1. This contradicts the hypothesis that there is no rainbow cycle of length n − 1 containing x1. Then … view at source ↗
Figure 3
Figure 3. Figure 3: The rainbow cycle Cst(1) of length n − 2 Proof. By symmetry, we only need to prove the case of i = 1. By Claim 2.1, x4x5 −→Cnx1 is a rainbow path of order n − 2 such that all edges are strong edges. Fix two integers s ∈ [n] and t ∈ [n], if there are two integers a, b ∈ [n] \ {s, t} such that x1x4 ∈ E(Ga) ∪ E(Gb), then Cst(1) = x4x5 −→Cnx1x4 is the desired cycle. The claim follows. Then we assume that x1x4 … view at source ↗
Figure 4
Figure 4. Figure 4: The rainbow cycle of length ℓ − 2 so dn(x5, V (Cℓ)) + d7(x8, V (Cℓ)) ≤ ℓ − 1. Consequently, dn(x5, V \ V (Cℓ)) + d7(x8, V \ V (Cℓ)) ≥ n − ℓ + 1. Since |V \ V (Cℓ)| = n − ℓ, there is at least one vertex w ∈ V \ V (Cℓ) such that x5w ∈ E(Gn), wx8 ∈ E(G7). If w = z, then x1zx5 −→Cℓx1 is a rainbow cycle of length ℓ − 2 containing x1, see (4) of view at source ↗
read the original abstract

Let $ n \in \mathbb{N} $ with $ n \geq 3 $, and let $\mathcal{G} = \{G_i:i\in [n]\} $ be a family of $ n $-vertex graphs on a common vertex set $V$, where the graphs in the family do not need to be distinct. A graph $H$ with vertex set $V$ is \emph{rainbow} in $\mathcal{G}$ if there exists an injection $ \phi: E(H) \to [n] $ such that $e \in E(G_{\phi(e)})$ for every edge $e \in E(H)$, where $|E(H)|\leq n$. In 2020, Joos and Kim proved that $\mathcal{G}$ contains a rainbow Hamiltonian cycle under the Dirac-type condition. Recently, Liu, Chen, and Ma generalized this result by replacing the Dirac-type condition with a more general Ore-type condition involving degree sums of non-adjacent vertices: If $\sigma(\mathcal{G}) \geq n$, then $\mathcal{G}$ contains a rainbow Hamiltonian cycle, where the Ore-type condition $\sigma(\mathcal{G})$ is defined as follows: $ \sigma(\mathcal{G}) = \min\{d_p(u) + d_q(v) \mid uv \notin E(G_i) \text{ for some } i \in [n] \text{ and for all } p, q \in [n]\}. $ In this paper, under the Ore-type condition, we show that either each vertex of $V$ is contained in a rainbow cycle of length $\ell$ for every $\ell\in[4,n]$, or $G_1=\cdots=G_n=K_{\frac{n}{2},\frac{n}{2}}$. As a corollary, we deduce the rainbow pancyclicity of $\mathcal{G}$, which supports the famous meta-conjecture posed by Bondy. Furthermore, we prove rainbow vertex-pancyclicity of $\mathcal{G}$ under the Ore-type condition and provide an extremal graph family to show that the result is sharp.

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.

Referee Report

1 major / 2 minor

Summary. The manuscript proves that for a family 𝒢 = {G_i : i ∈ [n]} of n graphs on a common n-vertex set V with σ(𝒢) ≥ n, either every vertex of V lies in a rainbow cycle of length ℓ for each ℓ ∈ [4,n], or G_1 = ⋯ = G_n = K_{n/2,n/2}. As a corollary it obtains rainbow pancyclicity of 𝒢 (supporting Bondy's meta-conjecture) and rainbow vertex-pancyclicity, with the balanced complete bipartite family serving as the extremal example showing sharpness.

Significance. The result strengthens the 2020 Joos-Kim Dirac-type rainbow Hamilton cycle theorem and the subsequent Liu-Chen-Ma Ore-type generalization by moving from Hamiltonicity to full pancyclicity and vertex-pancyclicity. The extremal characterization is clean and the sharpness example is explicit. If the combinatorial case analysis is complete, the paper supplies a natural Ore-type pancyclicity theorem in the rainbow setting.

major comments (1)
  1. [§3] §3, proof of Theorem 1.1: the case division on the structure of the family when σ(𝒢) ≥ n appears to rule out mixed families (some G_i complete bipartite, others complete) by showing that any deviation from the all-K_{n/2,n/2} case forces the existence of the required rainbow cycles; however, the argument that no other extremal configurations preserve the minimum degree-sum threshold while blocking a rainbow C_ℓ for some vertex and some ℓ should be expanded with an explicit enumeration of the possible degree sequences that meet σ(𝒢) = n.
minor comments (2)
  1. [page 2] Definition of σ(𝒢) on page 2: the quantification 'for all p,q ∈ [n]' is slightly ambiguous on first reading; rephrasing to 'the minimum of d_p(u) + d_q(v) taken over all pairs u,v that are non-adjacent in at least one G_i and over all choices of p,q' would improve clarity.
  2. [Corollary 1.3] Corollary 1.3: the deduction of rainbow pancyclicity from the main theorem is immediate once vertex-pancyclicity is established, but a one-sentence reminder of the precise implication would help readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the positive assessment of the result. We address the single major comment below.

read point-by-point responses

  1. Referee: [§3] §3, proof of Theorem 1.1: the case division on the structure of the family when σ(𝒢) ≥ n appears to rule out mixed families (some G_i complete bipartite, others complete) by showing that any deviation from the all-K_{n/2,n/2} case forces the existence of the required rainbow cycles; however, the argument that no other extremal configurations preserve the minimum degree-sum threshold while blocking a rainbow C_ℓ for some vertex and some ℓ should be expanded with an explicit enumeration of the possible degree sequences that meet σ(𝒢) = n.

    Authors: We agree that an explicit enumeration of degree sequences satisfying σ(𝒢) = n would clarify the case analysis and strengthen the presentation. In the proof of Theorem 1.1, the argument already proceeds by cases on the structure of 𝒢: if the family is not identically {K_{n/2,n/2}}, then the Ore-type condition forces the existence of the rainbow cycles of all lengths ℓ ∈ [4,n] through every vertex, via a combination of path-extension arguments and rainbow adaptations of standard pancyclicity techniques. To make this ruling-out of other configurations fully transparent, we will add a short supplementary paragraph (or lemma) that enumerates the extremal degree sequences under σ(𝒢) = n and verifies that only the all-K_{n/2,n/2} family blocks the required cycles; any other sequence meeting the threshold permits the constructions. This addition will appear in the revised Section 3. revision: yes

Circularity Check

0 steps flagged

No circularity: standard extremal proof via independent combinatorial case analysis

full rationale

The derivation proceeds from the given Ore-type condition σ(𝒢) ≥ n by direct combinatorial arguments establishing the stated dichotomy (rainbow vertex-pancyclicity or the balanced complete bipartite family). Prior Hamiltonian results are cited from non-overlapping authors (Joos-Kim, Liu-Chen-Ma) and serve only as background; the pancyclicity extension is self-contained within the present case analysis. No fitted parameters, self-definitional loops, ansatz smuggling, or load-bearing self-citations appear. The skeptic concern about missed configurations is a potential completeness issue for the case analysis, not a circularity reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard graph theory definitions and the given degree condition; no free parameters, new entities, or ad-hoc axioms beyond domain assumptions are introduced in the abstract.

axioms (2)
  • standard math Standard definitions of undirected graphs, vertex degrees, cycles, and rainbow subgraphs.
    The paper operates within classical graph theory.
  • domain assumption The Ore-type condition σ(G) ≥ n is sufficient for the stated rainbow pancyclicity except in the extremal case.
    This is the central hypothesis whose sufficiency is claimed.

pith-pipeline@v0.9.0 · 5688 in / 1359 out tokens · 92794 ms · 2026-05-07T09:53:16.852169+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Aharoni, E

    R. Aharoni, E. Berger, M. Chudnovsky, D. Howard, and P. Seym our. Large rainbow matchings in general graphs. European Journal of Combinatorics , 79:222–227, 2019

    work page 2019

  2. [2]

    Aharoni, M

    R. Aharoni, M. DeVos, S. Gonz´ alez Hermosillo de la Maza, A. Monte jano, and R. ˇS´ amal. A rainbow version of Mantel’s theorem. Advances in Combinatorics , 2:12, 2020

    work page 2020

  3. [3]

    J. A. Bondy. Pancyclic graphs I. Journal of Combinatorial Theory, Series B , 11(1):80–84, 1971

    work page 1971

  4. [4]

    J. A. Bondy. Pancyclic graphs: Recent results. In A. Hajnal, R. Rado, and V. T. S´ os, editors, Infinite and Finite Sets , volume 10 of Colloquia Mathematica Societatis J´ anos 16 Bolyai, pages 181–187, Amsterdam, 1973. North-Holland. Proceedings of the Colloquium held in Keszthely, Hungary, 1973

    work page 1973

  5. [5]

    J. A. Bondy and U. S. R. Murty. Graph Theory. GTM 244, Springer, London, 2008

    work page 2008

  6. [6]

    Bradshaw

    P. Bradshaw. Transversals and bipancyclicity in bipartite graph f amilies. The Electronic Journal of Combinatorics , 28(4):#P4.25, Nov. 2021

    work page 2021

  7. [7]

    Chakraborti, J

    D. Chakraborti, J. Kim, H. Lee, and J. Seo. Transversal cycles and paths in tournaments. Combinatorica, 44(6):1381–1400, 2024

    work page 2024

  8. [8]

    Cheng, J

    Y. Cheng, J. Han, B. Wang, and G. Wang. Rainbow spanning struc tures in graph and hypergraph systems. Forum of Mathematics, Sigma , 11:e95, 2023

    work page 2023

  9. [9]

    Cheng, H

    Y. Cheng, H. Li, W. Sun, and G. Wang. Transversal hamilton cycle s in digraph collections. Combinatorics, Probability and Computing , 251:1–57, 2026

    work page 2026

  10. [10]

    Cheng, G

    Y. Cheng, G. Wang, and Y. Zhao. Rainbow pancyclicity in graph sy stems. The Electronic Journal of Combinatorics , 28(3):Paper No. P3.24, 2021

    work page 2021

  11. [11]

    G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, s3-2:69–81, 1952

    work page 1952

  12. [12]

    G. H. Fan. New sufficient conditions for cycles in graphs. Journal of Combinatorial Theory, Series B , 37:221–227, 1984

    work page 1984

  13. [13]

    Ferber, J

    A. Ferber, J. Han, and D. Mao. Dirac-type problem of rainbow m atchings and hamilton cycles in random graphs. arXiv preprint , 2022

    work page 2022

  14. [14]

    Ghouila-Houri

    A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit hamiltonien. Comptes Rendus de l’Acad´ emie des Sciences Paris, 251:495–497, 1960

    work page 1960

  15. [15]

    Joos and J

    F. Joos and J. Kim. On a rainbow version of dirac’s theorem. Bulletin of the London Mathematical Society, 52(3):498–504, 2020

    work page 2020

  16. [16]

    L. Li, P. Li, and X. Li. Rainbow structures in a collection of graphs with degree conditions. Journal of Graph Theory , 104:341–359, 2023

    work page 2023

  17. [17]

    L. Li, P. Li, and X. Li. Rainbow pancyclicity in a collection of graphs u nder the dirac-type condition. Acta Mathematica Sinica, English Series , 40(2):269–274, 2024

    work page 2024

  18. [18]

    S. Liu, G. Chen, and J. Ma. Hamiltonian transversal and dipancy clic transversal. Acta Mathematica Sinica (Chinese Series) , 2025. Accepted for publication

    work page 2025

  19. [19]

    Montgomery, A

    R. Montgomery, A. M¨ uyesser, and Y. Pehova. Transversal factors and spanning trees. Advanced in Combinatorics , 3:25, 2020. 25 pages. 17

    work page 2020

  20. [20]

    O. Ore. Note on Hamilton circuits. American Mathematical Monthly , 67:55, 1960. 18

    work page 1960