ABSTRACT
Letu andvbe twovertices of a graphG. Suppose that there exists a path fromu tov inG. The distance from u to v, written dG(u, v) or simply d(u, v), is the least length among all paths from u to v. Suppose that there exists no path from u to v inG. Then d(u, v)=∞. THEOREM 3.1 Assume that G is a graph. Then
1. d(u, v)≥ 0 and d(u, v)= 0 if and only if u= v 2. d(u, v)= d(v, u) for all u, v∈V (G) 3. d(u, v)≤ d(u,w)+ d(w, v) for all u, v,w∈V (G) (the triangle inequality)
Proof: The proof of (1) and (2) are obvious. We need to prove the third statement. Let u, v, and w be vertices of G. Let P be the shortest path from u to w and Q the shortest path from w to v in G. Then P followed by Q is a path W from u to v. Thus, d(u, v)≤ d(u,w)+ d(w, v).
