Given is a simple graph with $239$ vertices, such that it is not bipartite and each vertex has degree at least $3$. Find the smallest $k$, such that each odd cycle has length at most $k$.
Problem
Source: 239 MO 2021 (8-9).3
Tags: combinatorics
26.06.2021 14:52
Bump! Solution?
27.06.2021 15:11
First of all note that graph is bipartite iff all circles in it have even degree. So, in the problem it is given for avoid choosing $ k=0$. Now, I am trying to prove that $ k=3$ doesn't work, which I am sure is true. Edit: There is $39$ "type 1" figure in the graph , not $59$.
Attachments:

28.06.2021 11:26
Ok, so we are left to prove that we can't have a graph with $239$ vertices, each with degree at least $3$, such that each odd cycle in the graph is a triangle. Anyone?
28.06.2021 12:12
I think there exists an example for $k=3$. Take $59$ isolated $K_4$'s and number the remaining $3$ vertices as $1,2,3$. Now connect $1,2,3$ so that they form a $K_3$. Finally connect $1$ to a single vertex in the first $K_4$, connect $2$ to a single vertex in the second $K_4$ and connect $3$ to a single vertex in the third $K_4$. Now every vertex has degree $\geq 3$ and every odd cycle is a triangle.
28.06.2021 14:30
I think you are right. Really I didn't think about to give such a simple construction for $k=3$. I thank that is P3 and it shouldn't be such easy. Thank you!
09.09.2021 20:08
JBMO2020 wrote: Given is a simple graph with $239$ vertices, such that it is not bipartite and each vertex has degree at least $3$. Find the smallest $k$, such that each odd cycle has length at most $k$. are you sure that it is not at least $k$ instead of at most $k$ ?
25.08.2022 22:17
Actually, the problem turns out to be the following: Given is a non-bipartite graph with $239$ vertices, such that all vertices have degree at least $3$. Find the minimal $k$, such that it is always guaranteed to find a cycle with length at most $k$. Now I think the answer is $159$. Here is a proof that there is always a cycle of length at most $159$. Suppose that the smallest odd cycle has length at least $161$ (it is guaranteed to exist since the graph is not bipartite). Obviously this cycle doesn't have chords, so all edges coming out from them connect them with the rest $\leq 78$ vertices. The degree condition implies that we have that at least $161$ edges going to these $78$ vertices, so there is an vertex among them, which has three neighbors on the cycle. Now it's easy to see we have a smaller odd cycle, contradiction.