Eccentricity, Radius, and Diameter in Trees

Measuring Distances Across a Tree

A rooted tree gives a way to discuss depth and height relative to a chosen root. Eccentricity, radius and diameter instead describe distances across the whole graph, without privileging any root. They let us ask how far a vertex can be from its most distant vertex, how small that worst-case distance can be, and how long the greatest separation in the tree is.

All graphs in this tutorial are finite and simple. A path has no repeated vertices, and its length is its number of edges. A tree is a connected graph with no cycles. In a tree, there is a unique path between every pair of vertices: connectedness gives at least one path, and two distinct paths between the same vertices would contain a cycle.

Definition: Let $G$ be a nonempty connected graph. The eccentricity of $v\in V(G)$ is $\operatorname{ecc}(v)=\max_{u\in V(G)}d(v,u)$. The diameter is $\operatorname{diam}(G)=\max_{v\in V(G)}\operatorname{ecc}(v)$, equivalently the greatest distance between any two vertices. The radius is $\operatorname{rad}(G)=\min_{v\in V(G)}\operatorname{ecc}(v)$.

These maxima and minima exist because the graph is finite and connected, so all distances are finite. A vertex at distance $\operatorname{ecc}(v)$ from $v$ is a farthest vertex from $v$; the unique path to it is a longest path starting at $v$. This does not mean that it is a longest path anywhere in the graph. The diameter is the length of a longest path in a tree: a path between vertices at greatest distance has that length, and every path has length at most the distance between its endpoints.

For the one-vertex tree, the only distance is $0$, so its eccentricity, radius and diameter are all $0$. The empty graph has no vertices over which to take the stated maximum or minimum, so these parameters are not defined here for it. We will work with nonempty trees.

Calculating the Parameters

Worked Example: A Path on Six Vertices

Let $T$ have vertex set $V(T)=\{1,2,3,4,5,6\}$ and edge set $E(T)=\{12,23,34,45,56\}$. This is the path $P_6$. In a path, the distance between $i$ and $j$ is $|i-j|$.

For vertex $1$, the distances to $1,2,3,4,5,6$ are $0,1,2,3,4,5$, so $\operatorname{ecc}(1)=5$. For vertex $2$, they are $1,0,1,2,3,4$, so $\operatorname{ecc}(2)=4$. For vertex $3$, they are $2,1,0,1,2,3$, so $\operatorname{ecc}(3)=3$. Reversing the path gives $\operatorname{ecc}(4)=3$, $\operatorname{ecc}(5)=4$, and $\operatorname{ecc}(6)=5$. Thus the eccentricities in vertex order are $5,4,3,3,4,5$.

The smallest of these values is $3$, and the largest is $5$. Hence $\operatorname{rad}(T)=3$ and $\operatorname{diam}(T)=5$. As a check, the path from $1$ to $6$ has five edges, and no pair of vertices can be farther apart: their labels differ by at most $5$.

Worked Example: A Star

Let $T$ have vertex set $V(T)=\{c,a,b,d,e\}$ and edge set $E(T)=\{ca,cb,cd,ce\}$. The vertex $c$ is adjacent to each of the four leaves $a,b,d,e$, and there are no other edges.

The distance from $c$ to each leaf is $1$, so $\operatorname{ecc}(c)=1$. For any leaf, the distances to itself, $c$, and each of the other three leaves are respectively $0,1,2$. For example, the path from $a$ to $b$ is $a,c,b$, of length $2$, so $\operatorname{ecc}(a)=2$; the same calculation gives eccentricity $2$ for $b,d,e$. Therefore $\operatorname{rad}(T)=1$ and $\operatorname{diam}(T)=2$.

Check: the greatest distance is between two distinct leaves. Each such path uses exactly two edges, while the distance from the center to a leaf is only one edge. This confirms both the diameter and the listed eccentricities.

Worked Example: An Unevenly Branching Tree

Let $T$ have vertex set $V(T)=\{a,b,c,d,e,f,g\}$ and edge set $E(T)=\{ab,bc,cd,be,bf,fg\}$. From $b$, one branch goes through $c$ to $d$, one ends at $a$, and one goes through $f$ to $g$; another ends at $e$.

From $a$, the distances to $b,c,d,e,f,g$ are $1,2,3,2,2,3$, so $\operatorname{ecc}(a)=3$. From $b$, the distances to $a,c,d,e,f,g$ are $1,1,2,1,1,2$, so $\operatorname{ecc}(b)=2$. From $c$, the distances to $a,b,d,e,f,g$ are $2,1,1,2,2,3$, so $\operatorname{ecc}(c)=3$. From $d$, the distances to $a,b,c,e,f,g$ are $3,2,1,3,3,4$, so $\operatorname{ecc}(d)=4$.

For the remaining vertices, from $e$ the distances to $a,b,c,d,f,g$ are $2,1,2,3,2,3$, giving $\operatorname{ecc}(e)=3$. From $f$, the distances to $a,b,c,d,e,g$ are $2,1,2,3,2,1$, giving $\operatorname{ecc}(f)=3$. From $g$, the distances to $a,b,c,d,e,f$ are $3,2,3,4,3,1$, giving $\operatorname{ecc}(g)=4$. The radius is therefore $2$, attained at $b$, and the diameter is $4$.

Check: the path $d,c,b,f,g$ has four edges. The listed eccentricities show that no vertex is more than four edges from another, so this path realizes the diameter.

Why Diameter Endpoints Determine Eccentricity

A useful feature of trees is that one pair of vertices suffices to calculate the eccentricity of every vertex. The pair must be the endpoints of a diameter—that is, vertices $a,b$ whose distance is the diameter $D$. The result depends on the unique-path structure of a tree.

Theorem: Let $T$ be a nonempty finite tree, and let $a,b$ be endpoints of a diameter of length $D=d(a,b)$. For every vertex $x\in V(T)$, $\operatorname{ecc}(x)=\max\{d(x,a),d(x,b)\}$.

Proof. If $T$ has one vertex, then $a=b=x$, and all three quantities in the claimed equality are $0$. Now suppose $T$ has at least two vertices. Let $P$ be the unique path from $a$ to $b$, of length $D$. For any vertex $z$, the path from $z$ to $P$ first meets $P$ at a unique vertex $p_z$. This vertex is unique: if paths from $z$ joined $P$ at two different vertices, their union with the section of $P$ between those vertices would contain a cycle.

Fix $x$ and any $y$. Write $p_x,p_y$ for their meeting vertices on $P$, let $i=d(a,p_x)$, $j=d(a,p_y)$, $h=d(x,p_x)$, and $k=d(y,p_y)$. The unique path from $x$ to $y$ consists of the route from $x$ to $p_x$, the section of $P$ between $p_x$ and $p_y$, and the route from $p_y$ to $y$. Thus $d(x,y)=h+|i-j|+k$. Since $a,b$ are diameter endpoints, $d(a,y)=j+k\le D$ and $d(b,y)=D-j+k\le D$. In particular, $k\le D-j$ and $k\le j$.

If $j\ge i$, then $k+|i-j|=k+j-i\le D-j+j-i=D-i$. If $j\le i$, then $k+|i-j|=k+i-j\le j+i-j=i$. In either case, $k+|i-j|\le\max\{i,D-i\}$. It follows that $$ d(x,y)\le h+\max\{i,D-i\}=\max\{h+i,h+D-i\}=\max\{d(x,a),d(x,b)\}. $$ This holds for every $y$, so $\operatorname{ecc}(x)\le\max\{d(x,a),d(x,b)\}$. The reverse inequality follows because both $a$ and $b$ are vertices of $T$, and eccentricity is the maximum distance from $x$ to any vertex. Therefore equality holds. $\square$

The theorem gives a direct calculation rule: once a diameter path is known, find the distances from a vertex to its two endpoints and take the larger. It is important that $a,b$ are diameter endpoints; an arbitrary pair does not in general determine all eccentricities.

Worked Example: Using Diameter Endpoints

Return to the tree with edges $ab,bc,cd,be,bf,fg$. Its diameter endpoints are $d$ and $g$, at distance $4$. For each vertex $x$, compute the two endpoint distances and take their maximum:

For $a$, $d(a,d)=3$ and $d(a,g)=3$, so the maximum is $3$. For $b$, $d(b,d)=2$ and $d(b,g)=2$, so it is $2$. For $c$, the distances are $1$ and $3$, so it is $3$. For $d$, they are $0$ and $4$, so it is $4$. For $e$, they are $3$ and $3$, so it is $3$. For $f$, they are $3$ and $1$, so it is $3$. For $g$, they are $4$ and $0$, so it is $4$.

These results reproduce the eccentricities $3,2,3,4,3,3,4$ found by checking distances to all vertices in the previous example. In particular, their minimum is $2$ and their maximum is $4$, again giving radius $2$ and diameter $4$.

The Radius–Diameter Relation for Trees

The radius and diameter are not independent in a tree. The diameter forces every vertex to be at least about halfway from one of its endpoints, while a vertex near the midpoint of a diameter path is at most that far from both endpoints.

Theorem: If $T$ is a nonempty finite tree with diameter $D$, then $\operatorname{rad}(T)=\lceil D/2\rceil$.

Proof. If $D=0$, the tree has one vertex, so its radius is $0=\lceil 0/2\rceil$. Suppose $D\ge1$, and choose diameter endpoints $a,b$. For any vertex $v$, the triangle inequality gives $D=d(a,b)\le d(a,v)+d(v,b)$. Each of the two distances on the right is at most $\operatorname{ecc}(v)$, so $D\le2\operatorname{ecc}(v)$. Since eccentricity is an integer, $\operatorname{ecc}(v)\ge\lceil D/2\rceil$. Taking the minimum over $v$ gives $\operatorname{rad}(T)\ge\lceil D/2\rceil$.

For the other inequality, choose a vertex $v$ on the $a$-to-$b$ path with $d(a,v)=\lfloor D/2\rfloor$. Then $d(v,b)=D-\lfloor D/2\rfloor=\lceil D/2\rceil$. The diameter-endpoint theorem gives $\operatorname{ecc}(v)=\max\{d(v,a),d(v,b)\}=\lceil D/2\rceil$. Thus $\operatorname{rad}(T)\le\lceil D/2\rceil$, and combining the two inequalities proves the equality. $\square$

A Common Pitfall

Do not confuse height from a chosen root with diameter. For the unevenly branching tree above, suppose we root at $b$. The farthest vertices from $b$ are $d$ and $g$, each at distance $2$, so the height from that root is $2$. A mistaken calculation might report diameter $2$. But the path $d,c,b,f,g$ has length $4$, and the endpoint distances $d(d,g)=4$ confirm that the diameter is $4$. Rooted height measures distance from one selected vertex; diameter measures the greatest distance over all pairs.

For a tree, a reliable approach is to keep the quantities distinct: compute eccentricity by taking the farthest distance from each vertex, radius by taking the smallest eccentricity, and diameter by taking the largest. Once a diameter pair is established, the theorem reduces the eccentricity calculation for every vertex to two distances.

Check Your Understanding

Use the definitions and results above to answer these questions.

For the path $P_5$ with vertex set $\{1,2,3,4,5\}$ and edges $\{12,23,34,45\}$, find every eccentricity, the radius and the diameter.
A tree has diameter $7$. What is its radius, and why must every vertex have eccentricity at least that value?
In the tree with edges $12,23,24,45$, verify that vertices $1$ and $5$ are diameter endpoints, then use them to find the eccentricity of each vertex.
Explain why the eccentricity of a vertex is the length of a longest path starting at that vertex, but need not be the length of a longest path in the whole tree.