2
$\begingroup$

I have difficulties in understanding the proof for the following theorem.

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

Q:The first question why is actually $2\diam(G)+1$, intuitively it should be at most $2\diam(G)$, just the longest distance between two vertices back and forward.

Proof. Let $C$ be a shortest cycle in $G$. If $g(G) \geq 2\diam G+2$, then $C$ has two vertices whose distance in $C$ is at least $\diam G+1$. In $G$, these vertices have a lesser distance;

Q: Why the distance in $C$ should be different from distance $G$, by definition $C$ is a shortest circle in $G$, so $C$ is based on vertices of $G$.

any shortest path $P$ between them is therefore not a subgraph of $C$. Thus, $P$ contains a $C$-path $xPy$. Together with a shorter of the two $x-y$ paths in $C$, this path $xPy$ forms a shorter cycle than $C$, a contradiction.

I would appreciate if anyone would give more details regarding this proof.

$\endgroup$

3 Answers 3

5
$\begingroup$

I apologize in advance for my proof seeming pedantic, but virtually every "proof" I have seen in textbooks, or posted online, is incorrect. The idea behind the proof is straightforward enough, but one must exercise great care in its execution. So here goes ...

Set $g=girth(G)$ and $d=diam(G)$. We need to prove that $g$ is at most 2d+1. By way of contradiction, assume that $g$ is at least $2d+2$.

Let $C$ be a $g$-cycle in $G$, with consecutive vertices $x_0, x_1, x_2,..., x_{g-1}$. Denote by $P_C$ a shortest path along $C$ that has end-vertices $x_0$ and $x_{d+1}$. Note that when $g>2d+2$ this path is uniquely defined, whereas for $g=2d+2$ there are two such shortest paths. In either case, we may always choose $P_C$ to be the path having consecutive vertices $x_0, x_1, x_2,...,x_{d+1}$.

Set $t=dist_G(x_0,x_{d+1})$, and let $P$ be a path in $G$ from $x_0$ to $x_{d+1}$ with consecutive vertices $y_0(=x_0), y_1, y_2,...,y_{t-1}, y_t(=x_{d+1})$. By definition of diameter, $t \leq d$.

Let $j$ be the minimum value for which $y_j \neq x_j$. (Note that this implies that $x_i = y_i \forall i < j$.) Such a $j$ must exist, since otherwise we would have $P=P_C$, a contradiction since $P$ and $P_C$ have different lengths.

Now, among all values strictly greater than $j$, let $k$ be the minimal value for which $y_k$ lies on $P_C$. Such a $k$ must exist because $y_t (=x_{d+1})$ lies on $P_C$.

Thus $y_k= x_m$ for some $m \leq d+1$.

Now suppose $m < j$. Then by minimality of $j$, we have $y_k=x_m=y_m$. But this is impossible since $k>j>m$, and a path cannot have repeated vertices. We conclude that $m \geq j$.

At this point, we may construct the cycle with consecutive vertices

$$y_j, y_{j+1},..., y_k(=x_m), x_{m-1}, x_{m-2},...,x_{j-1}(=y_{j-1})$$

The length of this cycle is $m-j+1+k-j+1$ which is smaller than $g$. The easiest way to see this, is to note that $x_{j-1}, x_j,..., x_m$ is a portion of the path $P_C$, hence its length is at most $d+1$. Also note that $y_{j-1}, y_{j},..., y_k$ is a portion of the path $P$, hence its length at most $d$. Thus this cycle has length at most $2d+1$, a contradiction to our assumption that $g$ is at least $2d+2$.

$\endgroup$
1
  • $\begingroup$ @Brian, I'm sorry but I just joined up here a few days ago and I don't have enough points to just comment directly to your answer. You need to repair it a bit. Where you say that by definition d(u,v)≤g(G), that's certainly true but it's not strong enough to complete your argument. You really need d(u,v)≤diam(G) (equal to roughly half the girth). This is because later on, where you say the two paths from u to v in C both have length at least g(G)+1, you really mean to say they have length at least diam(G) + 1. $\endgroup$
    – Doc
    Sep 16, 2013 at 4:14
2
$\begingroup$

For your first question, look at $C_{2n+1}$, the cycle graph on $2n+1$ vertices. Its diameter is $n$, since the distance between two vertices maximally far apart is only $n$: there is a path of length $n+1$ between them, but it’s the longer way round the cycle. The girth, however, is clearly $2n+1$. The extra $+1$ is needed to cover this situation.

For your second question, let $u$ and $v$ be the two vertices in question. By definition $d(u,v)\le\operatorname{diam}(G)$, so there is a path $P$ from $u$ to $v$ in $G$ whose length is at most $\operatorname{diam}(G)$. The two paths from $u$ to $v$ in $C$ both have length at least $g(G)+1$, so $P$ is different from both of them.

$\endgroup$
3
  • $\begingroup$ "By definition, d(u,v)≤g(G), so there is a path P from u to v in G whose length is at most g(G)". Could you please explain why is d(u,v)≤g(G)? And why does such a path exist as mentioned in the above statement? $\endgroup$
    – RagingBull
    Sep 16, 2015 at 10:33
  • $\begingroup$ @Basant: Actually, $g(G)$ was an error on my part: it was supposed to be the diameter of $G$, not the girth, and I’ve now corrected it. $\endgroup$ Sep 16, 2015 at 10:47
  • $\begingroup$ Oh I see!Thank you :) $\endgroup$
    – RagingBull
    Sep 16, 2015 at 11:20
-1
$\begingroup$

$\def\diam{\operatorname{diam}}$For the first question: If $n$ is odd then $g(C_n)=2\diam(C_n)+1$ and if $n$ is even then $g(C_n)=2\diam(C_n)$. In any case, $g(C_n)\leq 2\diam(C_n) +1$. For any subgraph $H$ of a graph $G$, if $d_H(u,v) = d_G(u,v)$ for all $u,v \in H$ then $\diam(H) \leq \diam(G)$. If $C_n$ is a girth cycle of $G$ then $d_{C_n}(u,v) = d_G(u,v)$ for all $u,v \in C_n$ (this needs proof but is straightforward). Suppose that $C_n$ is girth cycle of $G$. Then

$g(G) = g(C_n)\leq 2\diam(C_n) + 1 \leq 2\diam(G)+1.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.