An arXiv version 1 preprint dated 20 August 2026 reports an exact answer to a problem in directed graph theory. For an n-vertex graph in the paper’s stated range, the minimum semidegree needed to ensure that every vertex lies on a directed cycle of length 3q is ⌈n/3⌉, for q ≥ 2.
The objects are finite oriented graphs—simple graphs with a direction assigned to each edge. In plain terms, minimum semidegree tracks the weakest vertex when its incoming and outgoing directed connections are counted; the theorem sets that floor at the rounded-up one-third mark.
A sharp boundary, with a size condition
The size condition is piecewise. The proof gives n0(2)=37, n0(3)=97, and n0(q)=45q−8 for q ≥ 4. These are sufficient cutoffs, not established optimal ones.
The one-unit gap below the threshold is real in an explicit construction. Three independent parts, V1, V2 and V3, are oriented cyclically on n−1 vertices; a new vertex u is then given V1→u→V2 and no arcs between u and V3. The construction has minimum semidegree ⌊(n−1)/3⌋=⌈n/3⌉−1. Every directed cycle through u has length 1 modulo 3, so u lies on no cycle of length 3q.
A short-path bridge
An important intermediate result concerns short paths. If the minimum semidegree is d, with d ≥ 3 and 7d ≥ 2N+3, every ordered pair of distinct vertices is joined by a directed path of length 3, 4 or 5.
The argument compares equally sized sets of vertices reached into and out of a chosen point. It restricts which arcs can cross successive layers, counts the available in- and out-degrees, and derives a contradiction from a quadratic inequality when no short path exists.
The short-path bound is also tight in the paper’s stated senses. For every c ≥ 2, an oriented graph with N=7c−1 vertices and minimum semidegree 2c can contain an ordered pair with no directed path of length 3, 4 or 5. In that formulation, the additive +3 cannot be reduced to +2, and the corresponding asymptotic coefficient 21 is best possible.
For orders divisible by 3, written n=3m, the proof separates cases according to whether out-neighborhoods are independent. Balanced-cut cases are finished with row-family classifications and matching arguments, while a butterfly case is handled by dedicated lemmas.
Bounds beyond the main case
The paper also gives a linear bound for other cycle lengths. For every ℓ ≥ 7, n ≥ 15ℓ−60 together with minimum semidegree ⌊n/3⌋+1 guarantees a directed cycle of length ℓ through every vertex.
When q ≥ 3 and n is not divisible by 3, a separate condition is given: n ≥ 45q−60 and minimum semidegree at least ⌈n/3⌉ guarantee a directed cycle of length 3q through every vertex.
The cutoff is still unsettled
For q ≥ 4, the order-and-minimum-semidegree-only argument cannot lower 45q−8 to 45q−9, and the smallest coefficient γ in a condition of the form n ≥ γq + O(1) remains open.
Paper data and sources
Original title: The Prescribed-Vertex Semidegree Threshold for Directed $3q$-Cycles in Oriented Graphs
Authors: Zhenhua Lyu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text