Is the following true:
A maximal graph $G$ with no cycles of length at least $k+1$ has $|V(G)| \leq k$ or has a cut-vertex when $k \geq 2$.
Here maximal is taken to mean that no edge can be added to $G$ without introducing a cycle of length at least $k+1$, we assume also that $G$ is connected. Nota bene: the statement might actually not be true but from trial and error I suspect that it is.
Obviously, when $|V(G)| \leq k$ such a maximal graph is the complete graph $K_{|V(G)|}$ which has no cut vertex.
Assume that $|V(G)| > k$ and that $G$ has no cycles of length at least $k+1$ and is maximal. I want to show that $G$ contains $K_k$ as an induced subgraph. Then, one of the vertices of this $K_k$ must be a cut-vertex.
By Menger's theorem, there exists $u,v\in V$ such that there are two disjoint paths $P_1$ and $P_2$ from $u$ to $v$. We have that
\begin{equation}
|P_1| + |P_2| – 2\leq k,
\end{equation}
where $|P_1|$ counts the number of vertices in $P_1$. Now I want to show that the subgraph induced by $ P:= V(P_1) \cup V(P_2)$ is actually a complete graph. I think that I can then finish the argument. So, assume that some edge is missing between $v_1 \in P_1 $ and $v_2\in P_2$. As $G$ is maximal, the addition of the edge $v_1v_2$ would create a cycle $C$ of length at least $k+1$. Now, if this cycle is completely disjoint from $P \setminus \{v_1,v_2\}$, then we can use the two paths to find a cycle of lenght at least $k+1$ in the graph $G$ before adding the edge.
So assume that $C$ passes through some vertices in $P$. Now I do not know how to finish the argument as $C$ may pass through the vertices in $P_1$ and $P_2$ in any order switching back and forth between vertices in both paths and not encountering them in order. (How) Can the argument be finished?
Thanks in advance!
Best Answer
The claim is false for every integer $k\geq 4$, but it is easily seen to be true for $k\in\{2,3\}$. For $k\geq4$, let $G$ be the connected graph on $n$ vertices $v_1,v_2,\ldots,v_n$, where $n>k$ is an integer, such that the vertex-induced subgraph $G[v_1,v_2,\ldots,v_{k-1}]$ is a complete graph on $k-1$ vertices, and that there are $2(n-k+1)$ extra edges $\{v_i,v_1\}$, $\{v_i,v_{k-1}\}$ for $i=k,k+1,k+2,\ldots,n$. This graph is maximal with respect to the condition that there does not exist a cycle of length $k+1$, but $G$ has $n>k$ vertices and does not possess a cut vertex.