Recipe

Compute a vertex's eccentricity

Use when: you're given a connected graph and one specific vertex v, and asked for ecc(v)

Goal: the single largest distance from v to any other vertex in the graph

Taught in Eccentricity

Quick recipe

Confirm you're working within one connected component
List the distance from v to every other vertex
Take the maximum of that list

1
Make sure the graph, or at least $v$ 's own piece of it, is fully connected before computing anything.

Example

The two-triangles graph (edges $AB, AC, BC, CD, CE, DE$ ) is a single connected piece, so every distance from $A$ is finite.
- the graph is connected — every distance from $v$ is guaranteed finite, continue to Step 2
- the graph is disconnected — restrict the whole computation to $v$ 's own component before continuing
Why: an infinite distance to some other component can't be the "greatest finite distance" eccentricity is meant to report, so reachability has to be settled first.
2
For each other vertex $u$ , find $d(v,u)$ using Section 4's own distance procedure: a direct edge gives $1$ , otherwise search increasing path lengths.

Example

From $A$ on the two-triangles graph: $d(A,B)=1$ (direct edge), $d(A,C)=1$ (direct edge), $d(A,D)=2$ (via $A,C,D$ ), $d(A,E)=2$ (via $A,C,E$ ).

Why: eccentricity is defined as a maximum over every other vertex, so every one of those distances has to be found before the largest can be picked out.
3
Compare every distance found in Step 2 and keep the largest one; a tie for largest is fine, only the value itself matters.

Example

The four distances from $A$ are $1, 1, 2, 2$ ; the largest is $2$ , so $\operatorname{ecc}(A) = 2$ .

⚡ Shortcut

On a path graph $P_n$ , skip listing every distance individually. An end vertex always has eccentricity $n-1$ , the full length of the path. A vertex at position $i$ (counting from either end) has eccentricity $\max(i-1, n-i)$ , and the middle vertex minimizes that at $\lceil (n-1)/2 \rceil$ . For $P_5$ : an end vertex has eccentricity $4$ , and the middle vertex $C$ has eccentricity $\lceil 4/2 \rceil = 2$ , matching a full distance list without ever writing one out.

Why: eccentricity is exactly $\max_u d(v,u)$ by definition, not a count of vertices or edges touching $v$ .

Common mistakes

Stopping after finding one large distance instead of checking every other vertex for an even larger one.
Computing eccentricity on a disconnected graph without first restricting to the one vertex's own component.
Confusing eccentricity (a single number, the worst case for one vertex) with the full list of distances it was computed from.
Applying the path-graph shortcut to a graph that only looks like a path in a drawing but has an extra edge creating a shortcut of its own.