# Paths of length $k$ imply cycles

Fix an integer $$k\geq 2$$. In an undirected graph, any vertex can reach any other vertex via a path of length $$k$$. For which $$n$$ must the graph contain a cycle of length $$n$$?

If we consider the complete graph of size $$k+1$$, any vertex can reach any other vertex via a path of length $$k$$ by going through all of the remaining vertices. This graph has cycles of length $$3,4,\ldots, k+1$$, so all $$n\geq k+2$$ are out. A cycle can probably be constructed by first looking at a path from $$a$$ to $$b$$ of length $$k$$, then considering a path from some middle vertex to $$b$$. The difficulty is that this second path may go through vertices of the first path, so we cannot tell the length of the cycle that arises.

• Good question! You can show that there always needs to be a cycle of length $k+1$ (i.e., let $uv$ be an edge and $P$ a path of length $k$ between $u$ and $v$). I think there must always be a cycle of length less than $k$, but showing that (given $k$) there is a cycle of length $j<k$ for some fixed $j$ (allowing $j$ to be a function of $k$) seems quite challenging. – Mike Feb 26 '19 at 23:56

Take a "spiky $$n$$-cycle", by which I mean, an $$n$$-cycle with triangles adjoined at each edge. Here's a spiky $$6$$-cycle: Each spiky $$n$$-cycle has the property for $$k = n$$ (it's much easier to see this for yourself, than for me to write out a proof, sorry), and has cycles of length $$3$$, $$n$$, $$n + 1$$, and others that are too big to worry about. We can construct these for $$n \ge 3$$, so for $$k \ge 3$$, our list of possible necessary cycle lengths is shortened to $$3, k, k + 1$$.