The Triangle Inequality for Graph Distance

Why Graph Distance Satisfies a Triangle Inequality

Shortest paths need not pass through a chosen intermediate vertex. But if we travel from $u$ to $v$ along a shortest path and then from $v$ to $w$ along another shortest path, the combined route is a walk from $u$ to $w$. Its length gives an upper bound on the shortest possible route from $u$ to $w$. This simple idea puts a strong restriction on every graph distance table.

Throughout, graphs are finite, simple and connected. A path is a sequence of distinct vertices with consecutive vertices adjacent, and its length is its number of edges. For vertices $u,v$, the graph distance $d(u,v)$ is the length of a shortest $u$-$v$ path. In a connected finite graph, such a path exists for every pair of vertices. A single-vertex graph has distance $0$ from its vertex to itself; statements about distinct pairs are then vacuous.

Theorem (Triangle Inequality): For any vertices $u,v,w$ in a connected graph $G$, $$ d(u,w)\le d(u,v)+d(v,w). $$

Proof. Choose a shortest $u$-$v$ path of length $d(u,v)$ and a shortest $v$-$w$ path of length $d(v,w)$. Concatenating them gives a $u$-$w$ walk of length $d(u,v)+d(v,w)$. The walk might repeat vertices, so it need not itself be a path. However, removing portions between repeated occurrences of a vertex turns a walk into a path with the same endpoints and no greater length. Thus there is a $u$-$w$ path of length at most $d(u,v)+d(v,w)$. Since $d(u,w)$ is the length of a shortest such path, it is no greater than this bound. $\square$

The inequality does not claim that a shortest $u$-$w$ path goes through $v$. It says only that the route through $v$ supplies a possible walk, and the shortest route cannot be longer than that walk. Equality holds when the route through $v$ is itself no longer than any alternative route; strict inequality occurs when a shorter route avoids $v$.

Using the Inequality to Check a Table

A distance table for a connected graph must be symmetric, have zero on the diagonal, and have a positive integer in every off-diagonal entry. It must also satisfy the triangle inequality for every triple of vertices. For a fixed graph, there is a further requirement: each entry must agree with the shortest path length in that graph. The triangle inequality is a necessary check, not a replacement for computing or verifying those shortest paths.

For a triple $u,v,w$, it is enough to compare the largest of the three distances with the sum of the other two. For example, if the three values are $1,2,2$, the largest is $2$, and $2\le1+2$; the other two values are each at most the sum of the remaining pair. This checks all three inequalities for that triple.

Worked Example: Checking a Distance Table in a Given Graph

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,13\}$. The edges give distances $d(1,2)=1$, $d(2,3)=1$, $d(3,4)=1$, and $d(1,3)=1$. Vertex $4$ is not adjacent to $1$ or $2$; the paths $1,3,4$ and $2,3,4$ each have length $2$, so $d(1,4)=2$ and $d(2,4)=2$.

The resulting table is

\begin{array}{c|rrrr} d & 1&2&3&4\\ \hline 1&0&1&1&2\\ 2&1&0&1&2\\ 3&1&1&0&1\\ 4&2&2&1&0 \end{array}

Check the four triples. For $\{1,2,3\}$, the distances are $1,1,1$, and the largest value satisfies $1\le1+1=2$. For $\{1,2,4\}$, they are $1,2,2$, and $2\le1+2=3$. For $\{1,3,4\}$, they are $1,1,2$, and $2\le1+1=2$. For $\{2,3,4\}$, they are $1,1,2$, and $2\le1+1=2$. Thus every triple satisfies the triangle inequality.

Check: In the equality case, $d(1,4)=2=d(1,3)+d(3,4)=1+1$. In a strict case, $d(1,4)=2<d(1,2)+d(2,4)=1+2=3$. The table agrees with the edge set: entries equal to $1$ are precisely the adjacent pairs, and the two nonadjacent pairs have distance $2$.

Worked Example: Rejecting a Proposed Table

Suppose a proposed distance table on $V=\{a,b,c,d\}$ is

\begin{array}{c|rrrr} d & a&b&c&d\\ \hline a&0&1&3&2\\ b&1&0&1&2\\ c&3&1&0&1\\ d&2&2&1&0 \end{array}

The entries are symmetric, have zero diagonal, and are positive integers off the diagonal. But the triple $a,b,c$ violates the triangle inequality: the table claims $d(a,c)=3$, while $d(a,b)+d(b,c)=1+1=2$. The required inequality would be $3\le2$, which is false. Therefore no connected graph can have this table as its graph-distance table.

Check: Any graph with $d(a,b)=1$ and $d(b,c)=1$ has an edge $ab$ and an edge $bc$. These edges form an $a$-$c$ path of length $2$, so $d(a,c)\le2$, directly contradicting the proposed value $3$.

A Related Bound for Distances from One Vertex

Applying the triangle inequality in two different orders gives a useful way to compare distances from a fixed vertex. This bound can detect a suspicious entry even when a table is presented as distances from one root.

Theorem (Reverse Triangle Inequality): For any vertices $r,u,v$ in a connected graph, $$ \left|d(r,u)-d(r,v)\right|\le d(u,v). $$

Proof. The triangle inequality applied to the route from $r$ to $u$ through $v$ gives $d(r,u)\le d(r,v)+d(v,u)$. By symmetry of distance, $d(v,u)=d(u,v)$, so $d(r,u)-d(r,v)\le d(u,v)$. Interchanging $u$ and $v$ gives $d(r,v)-d(r,u)\le d(u,v)$. Both inequalities together say that the absolute value of the difference is at most $d(u,v)$, as required. $\square$

Worked Example: Comparing Distances from a Root

Let $G=(V,E)$ have $V=\{r,a,b,c,d\}$ and $E=\{ra,ab,bc,bd\}$. From $r$, the distances are $d(r,r)=0$, $d(r,a)=1$, $d(r,b)=2$, $d(r,c)=3$, and $d(r,d)=3$. The paths from $r$ to $c$ and $d$ are $r,a,b,c$ and $r,a,b,d$, respectively; their lengths are both $3$.

The remaining pair distances are $d(a,b)=1$, $d(a,c)=2$, $d(a,d)=2$, $d(b,c)=1$, $d(b,d)=1$, and $d(c,d)=2$. The last value comes from the path $c,b,d$ of length $2$. These values allow a direct check of the reverse triangle inequality for every distinct pair $u,v$:

For $r,a$, the difference is $|0-1|=1$, equal to $d(r,a)=1$.
For $r,b$, it is $|0-2|=2=d(r,b)$; for $r,c$, it is $|0-3|=3=d(r,c)$; and for $r,d$, it is $|0-3|=3=d(r,d)$.
For $a,b$, it is $|1-2|=1=d(a,b)$; for $a,c$, it is $|1-3|=2=d(a,c)$; and for $a,d$, it is $|1-3|=2=d(a,d)$.
For $b,c$, it is $|2-3|=1=d(b,c)$; for $b,d$, it is $|2-3|=1=d(b,d)$; and for $c,d$, it is $|3-3|=0\le2=d(c,d)$.

Check: In each pair, the absolute difference of the two root distances is no greater than the distance between the pair. For example, the root distances to $c$ and $d$ are equal, so their difference is $0$, while their mutual distance is $2$.

What a Successful Check Does—and Does Not—Show

If a proposed table violates even one triangle inequality, it cannot describe graph distances. If it passes all such inequalities, however, that does not prove it is correct for a specified graph. The graph’s edges determine which pairs have distance $1$, and other entries must agree with actual shortest paths.

Worked Example: Passing the Triangle Test but Failing for the Given Graph

Let $G=(V,E)$ have $V=\{o,a,b,c\}$ and $E=\{oa,ob,oc\}$. This is a star: each leaf is adjacent to $o$, and no two leaves are adjacent. Its actual distances between distinct leaves are $d(a,b)=2$, $d(a,c)=2$, and $d(b,c)=2$; for example, the path from $a$ to $b$ is $a,o,b$ and has length $2$.

Consider instead the proposed table with diagonal entries $0$ and every off-diagonal entry $1$. Every triangle test passes: for three distinct vertices, each side has value $1$, and $1\le1+1=2$. But this is not the distance table of the specified star, since it claims $d(a,b)=1$, which would require an edge $ab$, while $ab\notin E$.

Check: The triangle inequalities hold, but the proposed value $d(a,b)=1$ disagrees with the actual two-edge path $a,o,b$. Thus the table is not correct for this graph.

A practical check for a proposed table is therefore to proceed in stages: check symmetry, diagonal and off-diagonal values; test every triple for the triangle inequality; then, when the graph is specified, compare entries with its edges and shortest paths. For a table of distances from one fixed vertex, the reverse triangle inequality supplies an additional quick consistency check. These tests are useful because one failed inequality is enough to rule out a table, while passing the tests is only a reason to continue checking, not a certificate of correctness for a given graph.

Common mistake: It is incorrect to argue that a table is valid just because every triple satisfies the triangle inequality. In the star example, assigning distance $1$ to every pair passes that test but gives distance $1$ to two leaves that are not adjacent. The correction is to distinguish a general consistency test from verification against the actual graph.

Check Your Understanding

Use the triangle inequality and the definitions of graph distance to answer the questions.

A proposed table has $d(x,y)=2$, $d(y,z)=3$, and $d(x,z)=6$. Can it be a graph-distance table? State the inequality you use.
In a connected graph, $d(r,u)=4$ and $d(r,v)=1$. What lower bound does the reverse triangle inequality give for $d(u,v)$?
Explain why concatenating two shortest paths may produce a walk rather than a path, and why that still proves the triangle inequality.
Give a reason why passing all triangle checks does not by itself verify a table for a specified graph.
In the graph with $V=\{1,2,3\}$ and $E=\{12,23\}$, write its distance table and check the triangle inequality for the triple $1,2,3$.