# Lower bound on outdegree/indegree in oriented graph to guarantee cycle of length at least $k$

An oriented graph is a digraph without any self-loops, multiple arcs, or 2-cycles. What is the smallest minimum outdegree of an oriented graph on $n$ vertices that ensures there will always be a cycle of length at least $k$? Can the bound be improved if one includes the minimum indegree in the bound?

## 1 Answer

Out-degree $k-2$ is sufficient to force a directed cycle of length at least $k$. To see this, consider a longest directed path $P:=v_1v_2 \dots v_\ell$. Since $P$ is a longest path and there are no $2$-cycles, all out-neighbours of $v_\ell$ are among $\{v_1, \dots, v_{\ell-2}\}$. Since $v_\ell$ has at least $k-2$ out-neighbours, this gives a directed cycle of length at least $k$.

On the other hand, this bound cannot be improved too much. For example, out-degree $k$ is in general not strong enough to force a directed cycle of length $3k+1$. To see this, orient the complete multi-partite graph $K_{k,k,k}$ in the obvious way. Note that this example also has minimum in-degree $k$, so adding a minimum in-degree condition will not help too much.

• Wait... I don't get how the out-neighbors of $P$ must be in the path. What if $P$ were a subgraph of a spanning tree of a non-Hamiltonian graph? Then wouldn't there always be an out-neighbor not in the path? – Elliot Gorokhovsky Dec 11 '16 at 5:27
• Sorry, that was a typo. It should have read all out-neighbours of $v_\ell$. I edited it. – Tony Huynh Dec 11 '16 at 7:57
• OK, it's clear now. – Elliot Gorokhovsky Dec 11 '16 at 8:33