I am currently studying the textbook Graph Theory, fifth edition, by Reinhard Diestel. Chapter 1.3 Paths and cycles says the following:
Proposition 1.3.2. Every graph $G$ containing a cycle satisfies $g(G) \le 2 \text{diam}(G) + 1$.
Proof. Let $C$ be a shortest cycle in $G$. If $g(G) \ge 2 \text{diam}(G) + 2$, then $C$ has two vertices whose distance in $C$ is at least $\text{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 $x P y$. Together with the shorter of the two $x$–$y$ paths in $C$, this path $x P y$ forms a shorter cycle than $C$, a contradiction. $\square$
The minimum length of a cycle (contained) in a graph $G$ is the girth $g(G)$ of $G$. The greatest distance between any two vertices in $G$ is the diameter of $G$, denoted by $\text{diam}(G)$. Given a graph $H$, we call $P$ an $H$-path if $P$ is non-trivial and meets $H$ exactly in its ends.
I don't see how this proof makes sense. Since $C$ is the shortest cycle, how does it make sense to say that, in $G$, these vertices have a lesser distance? Since $C$ is only a subgraph of $G$, wouldn't these vertices have greater distance when considering the entire graph, $G$, rather than a subgraph of $G$, $C$? I also don't seem to understand how the part after this makes sense, so I'd also appreciate clarification on that.
Best Answer
Let's go through this step-by-step.
All that we need here is to take an arbitrary vertex $v$ on $C$, then take $\operatorname{diam}(G)+1$ steps around the cycle to get to a second vertex $w$. Going the other way around the cycle, we'd need $g(G) - (\operatorname{diam}(G)+1)$ steps to get from $v$ to $w$, which is also at least $\operatorname{diam}(G)+1$.
So, first of all, this is always the relationship we expect when $C$ is a subgraph of $G$. When we go from the subgraph $C$ to the entire graph $G$, all the $v$-$w$ paths that existed in $C$ still exist in $G$, so in particular whatever the shortest path was in $C$, it still exists in $G$. The shortest path in $G$ is at least as short as that, possibly shorter! So the distance between $v$ and $w$ can only decrease.
In this particular case, we also know that the distance between $v$ and $w$ in $G$ is at most $\operatorname{diam}(G)$, because that's part of the definition of the diameter: all distances in $G$ are at most $\operatorname{diam}(G)$.
There is a $v$-$w$ path in $G$ of length $\operatorname{diam}(G)$, but in $C$, the shortest $v$-$w$ path has length $\operatorname{diam}(G)+1$. Therefore a shortest $v$-$w$ path in $G$ cannot be contained in $C$; it must use at least one edge outside $C$. Fix a particular shortest $v$-$w$ path, and call it $P$.
I feel like this is glossing over several details, in particular, what $x$ and $y$ are.
Since $P$ is not contained in $C$, it must use at least one edge outside $C$. So:
We let $x P y$ be the segment of $P$ beginning at $x$ and ending at $y$. By construction, $x P y$ shares no edges with $C$, and no vertices other than $x$ and $y$.
We construct a new cycle - call it $C'$ - by following $x P y$ from $x$ to $y$, then following $C$ from $y$ back to $x$, in whatever the shorter direction is.
By assumption, the length of $C$ is $g(G)$, and by a further assumption, $g(G) \ge 2\operatorname{diam}(G)+2$. In particular, $g(G)$ is strictly bigger than $2\operatorname{diam}(G)$.
On the other hand, the length of $x P y$ is at most $\operatorname{diam}(G)$ (because it's at most the length of $P$). The length of the shorter path in $C$ going from $y$ back to $x$ is at most $\frac12 g(G)$. Therefore the length of $C'$ is at most $\operatorname{diam}(G) + \frac12 g(G)$.
Since $g(G) > 2 \operatorname{diam}(G)$, we have $\frac12 g(G) > \operatorname{diam}(G)$, so $$g(G) > \operatorname{diam}(G) + \frac12 g(G),$$ which exactly says that the length of $C$ is greater than the length of $C'$. This is a contradiction, because $C$ is supposed to be a shortest cycle in $G$, and here is $C'$ being shorter.