From Eccentricity to Diameter
The eccentricity of a vertex measures how far it is from its most distant vertex. The diameter extends this idea to the whole graph: it is the greatest eccentricity among the vertices. Thus it records the longest shortest-path distance that must be travelled between any two vertices. Several vertices can achieve this greatest value, so identifying all the peripheral vertices requires comparing every vertex’s eccentricity with the diameter.
Throughout, graphs are finite, simple and connected, and have at least one vertex. For vertices \(u\) and \(v\), \(d(u,v)\) is the length of a shortest \(u\)-\(v\) path; in particular, \(d(v,v)=0\). Since the graph is connected, every pair of vertices has a finite distance. Recall that the eccentricity of \(v\) is the greatest distance from \(v\) to any vertex of the graph.
The maximum in the definition exists because \(V(G)\) is finite and nonempty, so there is a finite, nonempty list of eccentricities to compare. A graph consisting of a single vertex has eccentricity \(0\): the only distance to check is \(d(v,v)=0\). Its diameter is therefore \(0\), and its one vertex is peripheral. The empty graph is excluded because there is no vertex eccentricity to maximize. Disconnected graphs are excluded here because some vertex pairs have no path between them; the connected case is the setting for the distance calculations in this tutorial.
Diameter as a Greatest Pairwise Distance
Proof. For each fixed vertex \(u\), its eccentricity is \(\operatorname{ecc}(u)=\max_{v\in V(G)}d(u,v)\). Taking the maximum over all \(u\) gives \(\max_{u\in V(G)}\max_{v\in V(G)}d(u,v)\), which is precisely the greatest distance over all ordered pairs of vertices. By definition, this is \(\operatorname{diam}G\). Now suppose \(u\) is peripheral. Then \(\operatorname{ecc}(u)=\operatorname{diam}G\); because the maximum defining \(\operatorname{ecc}(u)\) is attained on the finite nonempty vertex set, some \(v\) satisfies \(d(u,v)=\operatorname{diam}G\). Conversely, if such a \(v\) exists, then \(\operatorname{ecc}(u)\ge d(u,v)=\operatorname{diam}G\). The definition of diameter also gives \(\operatorname{ecc}(u)\le\operatorname{diam}G\), so equality holds and \(u\) is peripheral. \(\square\)
This result gives two equivalent ways to calculate diameter: find every vertex eccentricity and take the largest, or find the greatest entry in the full distance table. The eccentricity approach also directly identifies the peripheral vertices: retain exactly the vertices whose row maximum equals the graph’s diameter.
Worked Example: A Path with Two Peripheral Vertices
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). This is a path. Between vertices \(i\) and \(j\), there is a unique path, so \(d(i,j)=|i-j|\). Substituting the vertex labels into this formula gives the distance table:
| \(d(u,v)\) | \(v=1\) | \(v=2\) | \(v=3\) | \(v=4\) | \(v=5\) | \(\operatorname{ecc}(u)\) |
|---|---|---|---|---|---|---|
| \(u=1\) | 0 | 1 | 2 | 3 | 4 | 4 |
| \(u=2\) | 1 | 0 | 1 | 2 | 3 | 3 |
| \(u=3\) | 2 | 1 | 0 | 1 | 2 | 2 |
| \(u=4\) | 3 | 2 | 1 | 0 | 1 | 3 |
| \(u=5\) | 4 | 3 | 2 | 1 | 0 | 4 |
For instance, the entries in the first row come from \(|1-1|=0\), \(|1-2|=1\), \(|1-3|=2\), \(|1-4|=3\), and \(|1-5|=4\); its row maximum is \(4\). The other rows follow by the same formula: their row maxima are \(3,2,3,4\), respectively. Therefore \(\operatorname{diam}G=\max\{4,3,2,3,4\}=4\), and the peripheral vertices are \(1\) and \(5\).
Check: the greatest table entry is \(4\), attained at \(d(1,5)=|1-5|=4\) and \(d(5,1)=|5-1|=4\). This agrees with the diameter and shows that each peripheral vertex is an endpoint of a pair at distance \(4\).
Finding Eccentricities from Distance Layers
A distance table can be built by listing, for each starting vertex, the vertices at each successive distance. The vertices at distance \(0\) consist of the starting vertex itself. The vertices at distance \(1\) are its neighbors; vertices first reached after another step have distance \(2\), and so on. Once every vertex has been reached, the largest layer number is the starting vertex’s eccentricity. For a small graph, repeating this process from each vertex makes the comparison explicit.
Worked Example: A Star with Three Peripheral Vertices
Let \(G=(V,E)\), where \(V=\{c,a,b,d\}\) and \(E=\{ca,cb,cd\}\). The vertex \(c\) is joined to each of the three leaves \(a,b,d\), and there are no other edges. From \(c\), the distance layers are \(\{c\}\) at distance \(0\) and \(\{a,b,d\}\) at distance \(1\). Hence \(d(c,a)=d(c,b)=d(c,d)=1\) and \(\operatorname{ecc}(c)=1\).
From \(a\), the layers are \(\{a\}\) at distance \(0\), \(\{c\}\) at distance \(1\), and \(\{b,d\}\) at distance \(2\). The length-two routes to the other leaves are \(a,c,b\) and \(a,c,d\); no length-one route exists because neither \(ab\) nor \(ad\) is an edge. Thus \(d(a,c)=1\), \(d(a,b)=d(a,d)=2\), and \(\operatorname{ecc}(a)=2\). The same layer calculation from \(b\) gives \(\{b\}\), then \(\{c\}\), then \(\{a,d\}\), so \(\operatorname{ecc}(b)=2\). From \(d\) the layers are \(\{d\}\), then \(\{c\}\), then \(\{a,b\}\), so \(\operatorname{ecc}(d)=2\).
Therefore \(\operatorname{diam}G=\max\{1,2,2,2\}=2\), and the peripheral vertices are \(a,b,d\), not \(c\).
Check: every two distinct leaves are at distance \(2\), since their route passes through \(c\); for example, the route \(a,c,b\) has length \(2\). There are three unordered leaf pairs, \(ab,ad,bd\), and each has distance \(2\). All other distinct pairs are a leaf and \(c\), at distance \(1\). Thus the greatest pairwise distance is \(2\), independently confirming the diameter.
Worked Example: A Chord Changes Which Vertices Are Peripheral
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,13\}\). The edge \(13\) is a chord of the path \(1,2,3,4,5\). To calculate distances from \(1\), the layers are \(\{1\}\), \(\{2,3\}\), \(\{4\}\), \(\{5\}\), at distances \(0,1,2,3\). Thus its distances to \(2,3,4,5\) are \(1,1,2,3\).
From \(2\), the layers are \(\{2\}\), \(\{1,3\}\), \(\{4\}\), \(\{5\}\), again giving distances \(1,1,2,3\) to the other vertices. From \(3\), the layers are \(\{3\}\), \(\{1,2,4\}\), \(\{5\}\), giving distances \(1,1,1,2\). From \(4\), the layers are \(\{4\}\), \(\{3,5\}\), \(\{1,2\}\), giving distances \(1,1,2,2\). From \(5\), the layers are \(\{5\}\), \(\{4\}\), \(\{3\}\), \(\{1,2\}\), giving distances \(1,2,3,3\).
The complete table, with the row maximum recorded as the eccentricity, is therefore:
| \(d(u,v)\) | \(v=1\) | \(v=2\) | \(v=3\) | \(v=4\) | \(v=5\) | \(\operatorname{ecc}(u)\) |
|---|---|---|---|---|---|---|
| \(u=1\) | 0 | 1 | 1 | 2 | 3 | 3 |
| \(u=2\) | 1 | 0 | 1 | 2 | 3 | 3 |
| \(u=3\) | 1 | 1 | 0 | 1 | 2 | 2 |
| \(u=4\) | 2 | 2 | 1 | 0 | 1 | 2 |
| \(u=5\) | 3 | 3 | 2 | 1 | 0 | 3 |
Taking the largest row maximum gives \(\operatorname{diam}G=\max\{3,3,2,2,3\}=3\). The peripheral vertices are \(1,2,5\), since exactly those vertices have eccentricity \(3\).
Check: the pair \(1,5\) has a shortest route \(1,3,4,5\) of length \(3\); the distance-table entry \(d(1,5)=3\) confirms that length. The table contains no entry greater than \(3\), so this pair realizes the diameter and no pair is farther apart.
What the Diameter Tells You
The diameter is a global measure: it concerns the most widely separated pair, rather than the distance from one chosen starting vertex. A small diameter means that even the most distant pair can be joined by a relatively short shortest path. A large diameter means that at least one pair is far apart in this sense. Peripheral vertices locate the vertices that attain the largest eccentricity; there may be one, several, or—in some graphs—all vertices.
The theorem gives a practical check on calculations. After finding the eccentricities, take their largest value \(D\). There must be at least one pair of vertices at distance \(D\), and each peripheral vertex must belong to such a pair. Conversely, if a vertex is an endpoint of a pair at distance \(D\), it is peripheral. This connects a row-based calculation to specific entries in the distance table.
Common Pitfalls
Do not confuse a long route with a large distance. Distance is the length of a shortest path, not the length of any route that happens to connect the vertices. In the chord example, the route \(1,2,3,4,5\) has length \(4\), but it is not a shortest route from \(1\) to \(5\): the route \(1,3,4,5\) has length \(3\). The correct distance is therefore \(3\), not \(4\).
Do not report only one peripheral vertex when there is a tie. In the path example, both \(1\) and \(5\) have eccentricity \(4\). Reporting only one would omit a vertex that attains the diameter. Compare every eccentricity with the largest value before listing the peripheral vertices.
Do not use one row maximum as the graph’s diameter. A row maximum is the eccentricity of its row’s vertex. The diameter is the largest of all row maxima. For the star, the row for \(c\) has maximum \(1\), but the rows for \(a,b,d\) have maximum \(2\), so the diameter is \(2\).
Check Your Understanding
For each question, use shortest-path distances and compare all relevant eccentricities.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), find the diameter and all peripheral vertices.
- For \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,cd\}\), find each eccentricity, the diameter and the peripheral vertices.
- Explain why a graph consisting of one vertex has diameter \(0\) and that vertex is peripheral.
- Prove that if \(G\) is connected and has at least two vertices, then its diameter is at least \(1\).
- Give a connected graph in which every vertex is peripheral, and verify this from its distances.