Every graph $G$ containing a cycle satisfies $g(G)\leq 2 \operatorname{diam}(G)+1$

graph theory

The following is from Graph Theory by Reinhard Diestel.

Every graph $G$ containing a cycle satisfies $g(G)\leq 2\operatorname{diam}(G)+1$.

Here $g(G)$ denotes the length of a shortest cycle contained in $G$.

The following is the author's proof.

Let $C$ be a shortest cycle in $G$. If $g(G)\geq 2\operatorname{diam}(G)+2$, then $C$ has two vertices whose distance in $C$ is at least $\operatorname{diam}(G)+1$. in $G$, these vertices have a lesser distance; any shortest path $P$ between them is therefore not a subgraph of $C$. Thus, $P$ contains a $C$-path $xPy$. Together with the shorter of the two $x-y$ paths in $C$, this path $xPy$ forms a shorter cycle than $C$, a contradiction.

I do not see how "in $G$, these vertices have a lesser distance" is possible. If this is the case, wouldn't the cycle containing this shorter path be shorter than $C$?

The following is my proof. Is this valid?

Let $C$ be a shortest cycle in $G$. If $g(G)\geq 2\operatorname{diam}(G)+2$, then $C$ has two vertices $x$ and $y$ whose distance in $C$ is at least $\operatorname{diam}(G)+1$. We know that $d_C(x,y)\geq d_G(x,y)$ since $C$ is a subgraph of $G$. Also, we know $d_G(x,y)$ cannot be less than $d_C(x,y)$ since $C$ is a shortest cycle in $G$. Thus, we conclude that $d_C(x,y)=d_G(x,y)\geq \operatorname{diam}(G)+1$, contradicting the definition of the diameter of $G$.

Best Answer

Your proof is the same as the Diestel proof, formulated only slightly differently. The line "in G, these vertices have a lesser distance" follows by definition of the diameter of $G$, and he then arrives exactly at the contradiction that you point out, which concludes his proof.

Your proof is also correct. In Diestel's proof, he follows the assumption of the truth of the diameter to arrive at a contradiction on the assumption on $C$. You do it the other way around, following the assumption on $C$ and arriving at a contradiction to the diameter. Both are equally valid, and essentially the same.