$k$-connected graph $G$ with $n$ vertices has a cycle of length at least $3k$ if $n\ge 3$ and $C_4\not\subseteq G$

Question

Problem 7.2.32 in Combinatorial Mathematics by Douglas B. West.

1. The complete question is:

Fix $k\ge 2$, and let $G$ be a $k$-connected graph with $n$ vertices. For $n\ge 3k$, prove that $G$ has a cycle of length at least $3k$ if $C_4\not\subseteq G$. (Kostochka)

2. My effort:

First, I thought it's an application of Dirac's Theorem (EDIT: Dirac's theorem on cycles in $k$-connected graphs), but after checking the proof of Dirac's, I realize the construction methods cannot be duplicated simply.

Please give me some hint if possible, thank you!

Answer 1

A rather standard exercise is to show that for $k\ge 2$, a $k$-connected graph with order at least $2k$ has a cycle of length at least $2k$. Let me provide a solution for this problem as a hint to yours.

Let $G$ be a $k$-connected graph with $k\ge 2$ and $n\ge 2k$. Consider a longest cycle $C$ in $G$, which has length at least $k$ by $k$-connectivity, and suppose for the sake of contradiction that $|C| < 2k$. Then there exists some vertex $v \in G\backslash C$. Since $|C| \ge k$, it follows by the fan lemma that there exists at least $k$ disjoint paths from $v$ to $C$. By the Pigeonhole principle, we can find adjacent vertices $x,y \in C$ such that $x$ and $y$ are both connected by disjoint paths to $v$. Then $x\rightarrow v \rightarrow y\overset{C}{\rightarrow} x$ is a cycle longer than $C$, contradicting its maximality.

Your result can be obtained using a rather straightforward modification of the above proof.