Caccetta–Häggkvist conjecture

Draw a finite network with at least one dot and one-way arrows between different dots, allowing at most one arrow in each direction for a given pair. A directed cycle follows arrows and returns to its start without repeating any other dot. Assume every dot has at least one outgoing choice. The conjecture says that having many such choices must force a short cycle: divide the total number of dots by the smallest outgoing-choice count and round up to a whole number. That should bound the cycle’s length. For six dots A through F arranged in a ring, draw arrows to the next dot and the dot after that. Every dot has two choices, and A→C→E→A is a three-arrow cycle, matching six divided by two.[1] [3]

If every point of a one-way network has several outgoing choices, must some route return quickly to its start? Take a finite nonempty directed graph with no self-arrows and at most one arrow per ordered pair of distinct vertices. This is a loopless simple digraph; opposite arrows are permitted and can form a two-cycle. Let $n$ count vertices and $d>0$ be the minimum outdegree, the smallest number of distinct outgoing neighbors at any vertex. A directed cycle has distinct vertices except for the repeated start at its end. Its shortest possible length is the directed girth $g$. The conjecture asserts $$g\le\left\lceil\frac{n}{d}\right\rceil.$$ Following arrows in any finite graph with positive outdegree eventually repeats a vertex, so some directed cycle is inevitable. The unknown is the sharper length bound. For vertices 0 through 5 with arrows from each vertex to the next one and next two cyclically, the cycle 0→2→4→0 has length three, and there is no one- or two-cycle. Its girth equals $\lceil6/2\rceil=3$.[1] [3]

The proposed bound remains unproved for general graphs.[1] [3]

The exact bound is needed for every permitted digraph. A guarantee with an extra additive constant can still allow a longer cycle, and a theorem for a special graph class does not cover arbitrary arrangements. The cited rainbow-cycle work studies a stronger labeled-edge problem and proves an approximation for fixed color-class size; that selected result does not establish the exact directed bound.[1] [3]

A loop records feedback: following arrows can bring a process back where it started. Outgoing-arrow counts reveal little about where the arrows lead. This is a basic test of how much a local count can reveal about the whole network, and part of the wider study of structures that become unavoidable under simple numerical constraints.[1] [3]

The directed and labeled-edge formulations have a concrete bridge. Replace each arrow by an undirected edge labeled with its source vertex. Keep separate edges with different labels if opposite arrows join the same pair. The outgoing neighbors at a vertex now form that label’s edge class. A rainbow cycle uses each label at most once; in this construction its labels force it to correspond to a directed cycle. Thus a sufficiently sharp rainbow-cycle theorem would imply the directed conjecture. This connects a branching condition to selecting a cycle with distinct labels, while retaining different quantifiers and approximation guarantees in the two problems.[1] [3]