Use part (a) to prove that diam(G) ≤ 2rad(G) for every graph G.

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5

풀이

(a)는 삼각부등식. 이전 풀이 참고.

Proof:

1. If there is no path $a \dots b$ or path $b \dots c$, then $d(a, b)$ or $d(b, c) = \infty$, so the inequality is trivially satisfied.

2. Otherwise, there exists a path $a \dots b$ of length $d(a, b)$ and a path $b \dots c$ of length $d(b, c)$. We may compose these two paths to form a longer walk $a \dots b \dots c$ of length $d(a, b) + d(b, c)$.

3. However, the distance $d(a, c)$ is the length of the shortest path $a \dots c$. Therefore, any walk $a \dots c$ is equal in length or longer than the shortest path. One such walk is the composition of the paths $a \dots b$ and $b \dots c$, satisfying the inequality:
   $$
   d(a, c) \leq d(a, b) + d(b, c).
   $$

Thus, the triangle inequality holds. $\qed$

---

Now we prove that $\text{diam}(G) \leq 2\text{rad}(G)$.

Proof:

1. Let $a \dots b$ be the longest path in $G$. Then there always exists a vertex $c$ that is a central vertex. By the triangle inequality, we have:
   $$
   d(a, b) \leq d(a, c) + d(c, b). \tag{3}
   $$

2. Since $a \dots b$ is the longest path, $d(a, b) = \text{diam}(G)$. Now:
   $$
   d(a, c) \leq \max_{x \in V} d(x, c) = \text{ecc}(c) = \text{rad}(G), \tag{4}
   $$
   where the rightmost equality holds because $c$ is central.

3. The same argument holds for $d(c, b)$.

4. Therefore:
   $$
   \text{diam}(G) = d(a, b) \leq d(a, c) + d(c, b) \leq \text{rad}(G) + \text{rad}(G) = 2\text{rad}(G). \tag{5}
   $$

Thus, $\text{diam}(G) \leq 2\text{rad}(G)$, as required.
$\qed$