(a) Prove that the distance function $d(u, v)$ on a pair of vertices of a graph satisfies the triangle inequality: $$d(u, v) + d(v, w) \geq d(u, w).$$

문제출처

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

풀이

1. The distance $d(u, v)$ between two vertices $u$ and $v$ is the length of the shortest path connecting $u$ and $v$.

2. Suppose $d(u, v) + d(v, w) < d(u, w)$.

• By definition, $d(u, v)$ is the length of the shortest path from $u$ to $v$, and $d(v, w)$ is the length of the shortest path from $v$ to $w$.
• However, $d(u, w)$ is the length of the shortest path from $u$ to $w$.
• If $d(u, v) + d(v, w)$ is less than $d(u, w)$, then $d(u, w)$ is not the shortest path between $u$ and $w$.

3. This contradicts the definition of $d(u, w)$. Therefore,
$$d(u, v) + d(v, w) \geq d(u, w).$$

Thus, the distance function $d(u, v)$ satisfies the triangle inequality.