3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mike Feb 26 '19 at 23:56
1
$\begingroup$

Not a complete answer, but maybe of some help.

Take a "spiky $n$-cycle", by which I mean, an $n$-cycle with triangles adjoined at each edge. Here's a spiky $6$-cycle:

enter image description here

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.