From Connectivity to Distance Summaries
Connectedness and distance questions are often linked: first determine which vertices can be reached from one another, then find the lengths of shortest paths between them. A distance table gathers those lengths in one place. Its row maxima give eccentricities, from which the radius, diameter, and central vertices can be read. This workshop puts those steps together on explicit graphs, including a disconnected graph where distances between components require care.
All graphs below are finite, simple, and undirected. A path is a sequence of distinct vertices in which each consecutive pair is an edge; its length is its number of edges. A graph is connected if every pair of vertices is joined by a path. Its connected components are its maximal connected subgraphs. For vertices in the same component, \(d(u,v)\) is the length of a shortest \(u\)-\(v\) path, and \(d(v,v)=0\).
For a disconnected graph, some pairs of vertices have no path between them. We use the extended convention \(d(u,v)=\infty\) for such pairs. Consequently, if the graph is disconnected and has at least one vertex, every vertex has global eccentricity \(\infty\), and its global radius and diameter are both \(\infty\). Those global values do not distinguish its components. When useful, we will instead calculate eccentricities, radius, diameter, and centers within each component. The empty graph has no vertices, so these vertex-based quantities are undefined for it.
A Reliable Route Through a Problem
For a connected graph, a distance table is a square table whose row and column labels are the vertices. The entry in row \(u\), column \(v\) is \(d(u,v)\). The diagonal entries are zero, and \(d(u,v)=d(v,u)\), because reversing a path from \(u\) to \(v\) gives a path of the same length from \(v\) to \(u\). To find distances from one chosen vertex \(r\), use layers: \(L_0=\{r\}\), and for each \(k\geq 0\), let \(L_{k+1}\) contain the vertices not already in an earlier layer that are adjacent to at least one vertex in \(L_k\).
Proof. We prove the statement by induction on \(k\). The only vertex at distance zero from \(r\) is \(r\), so the statement holds for \(L_0\). Suppose it holds through \(L_k\). If \(v\in L_{k+1}\), then \(v\) is adjacent to some \(w\in L_k\), so a shortest \(r\)-\(w\) path followed by \(wv\) has length \(k+1\). Hence \(d(r,v)\leq k+1\). The vertex \(v\) was not in any earlier layer, so by the induction hypothesis it is not at distance at most \(k\); therefore \(d(r,v)=k+1\). Conversely, if \(d(r,v)=k+1\), take a shortest \(r\)-\(v\) path and let \(w\) be the vertex immediately before \(v\). The initial segment ending at \(w\) has length \(k\) and is shortest: a shorter segment would give a shorter path to \(v\). Thus \(w\in L_k\), and \(v\), not having appeared earlier, is added to \(L_{k+1}\). This proves the claim for every layer. \(\square\)
The proof also explains how to extract a shortest path: starting at a vertex in \(L_k\), choose a neighbor in \(L_{k-1}\), then continue down through the layers until reaching \(r\). Reversing that sequence gives a path from \(r\), with exactly \(k\) edges. Each step decreases the distance by one, so the resulting path has the shortest possible length.
Worked Examples
Worked Example: A Connected Graph with a Longest Shortest Path
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ac,bc,bd,cd,de,ef\}\). Find its distance table, eccentricities, radius, diameter, central vertices, and peripheral vertices.
Start from \(a\). The layer calculation is:
| Distance from \(a\) | Layer | New vertices and reason |
|---|---|---|
| 0 | \(L_0=\{a\}\) | Starting vertex |
| 1 | \(L_1=\{b,c\}\) | \(ab\) and \(ac\) |
| 2 | \(L_2=\{d\}\) | \(d\) is adjacent to \(b\) and \(c\) |
| 3 | \(L_3=\{e\}\) | \(de\) |
| 4 | \(L_4=\{f\}\) | \(ef\) |
For example, following predecessors \(a,b,d,e,f\) gives an \(a\)-\(f\) path of length \(4\). The layers prove its length is shortest. Repeating the layer calculation from the other vertices gives the full table below. Symmetry supplies the matching entries on either side of the diagonal.
| \(d(u,v)\) | \(a\) | \(b\) | \(c\) | \(d\) | \(e\) | \(f\) |
|---|---|---|---|---|---|---|
| \(a\) | 0 | 1 | 1 | 2 | 3 | 4 |
| \(b\) | 1 | 0 | 1 | 1 | 2 | 3 |
| \(c\) | 1 | 1 | 0 | 1 | 2 | 3 |
| \(d\) | 2 | 1 | 1 | 0 | 1 | 2 |
| \(e\) | 3 | 2 | 2 | 1 | 0 | 1 |
| \(f\) | 4 | 3 | 3 | 2 | 1 | 0 |
Take the maximum in each row: \(\operatorname{ecc}(a)=4\), \(\operatorname{ecc}(b)=3\), \(\operatorname{ecc}(c)=3\), \(\operatorname{ecc}(d)=2\), \(\operatorname{ecc}(e)=3\), and \(\operatorname{ecc}(f)=4\). The smallest of these values is \(2\), so the radius is \(2\) and the only central vertex is \(d\). The largest is \(4\), so the diameter is \(4\) and the peripheral vertices are \(a\) and \(f\).
Check: The table gives \(d(a,f)=4\), witnessed by the path \(a,b,d,e,f\), which uses the four edges \(ab,bd,de,ef\). No row contains a distance greater than \(4\), so the diameter is indeed \(4\). The row for \(d\) has maximum \(2\), while every other row has maximum at least \(3\), confirming the radius and center.
Worked Example: Three Components and Two Kinds of Summary
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,23,13,34,56\}\). Find the components and report both componentwise and global distance summaries.
Vertices \(1,2,3,4\) are connected: \(1,2,3\) form a triangle and \(4\) is joined to \(3\). Vertices \(5,6\) form another component, and \(7\) is isolated. Thus the components have vertex sets \(\{1,2,3,4\}\), \(\{5,6\}\), and \(\{7\}\). In the first component the distance table is
| \(d(u,v)\) | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 2 |
| 2 | 1 | 0 | 1 | 2 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 2 | 2 | 1 | 0 |
The row maxima are \(2,2,1,2\). Therefore this component has radius \(1\), diameter \(2\), center \(\{3\}\), and peripheral vertices \(\{1,2,4\}\). For the component \(\{5,6\}\), the only nonzero distance is \(d(5,6)=1\), so both vertices have eccentricity \(1\); its radius and diameter are \(1\), and both vertices are central and peripheral. In the isolated-vertex component, the only distance is \(d(7,7)=0\), so its radius and diameter are \(0\), and vertex \(7\) is both central and peripheral within that component.
Check: There is no path from \(1\) to \(5\), so \(d(1,5)=\infty\). The same issue applies across each pair of distinct components. Under the stated global convention, every vertex has global eccentricity \(\infty\), and the global radius and diameter are \(\infty\). The finite componentwise summaries above retain useful information that the global values cannot provide.
Worked Example: Extracting a Shortest Path and Finding the Center
Let \(H=(V,E)\), where \(V=\{u,v,w,x,y\}\) and \(E=\{uv,uw,vw,wx,xy\}\). Build the distance table and find the center and peripheral vertices.
From \(u\), the layers are \(L_0=\{u\}\), \(L_1=\{v,w\}\), \(L_2=\{x\}\), and \(L_3=\{y\}\). The predecessor chain \(u,w,x,y\) gives a shortest path from \(u\) to \(y\) of length \(3\). The layer distances from each vertex give this table:
| \(d(u,v)\) | \(u\) | \(v\) | \(w\) | \(x\) | \(y\) |
|---|---|---|---|---|---|
| \(u\) | 0 | 1 | 1 | 2 | 3 |
| \(v\) | 1 | 0 | 1 | 2 | 3 |
| \(w\) | 1 | 1 | 0 | 1 | 2 |
| \(x\) | 2 | 2 | 1 | 0 | 1 |
| \(y\) | 3 | 3 | 2 | 1 | 0 |
The row maxima are \(\operatorname{ecc}(u)=3\), \(\operatorname{ecc}(v)=3\), \(\operatorname{ecc}(w)=2\), \(\operatorname{ecc}(x)=2\), and \(\operatorname{ecc}(y)=3\). Hence the radius is \(2\), the diameter is \(3\), the central vertices are \(w,x\), and the peripheral vertices are \(u,v,y\).
Check: The longest table entries are \(d(u,y)=3\) and \(d(v,y)=3\), witnessed by \(u,w,x,y\) and \(v,w,x,y\), respectively. The row maxima for \(w\) and \(x\) are both \(2\); each other row has maximum \(3\). These entries verify the radius, diameter, center, and peripheral set.
Reading the Results Correctly
For a connected graph, once the table is complete, the summary calculation is systematic: take the maximum in each row to obtain that vertex’s eccentricity; take the minimum of those row maxima for the radius; and take their maximum for the diameter. The vertices attaining the minimum are central, and those attaining the maximum are peripheral. Ties are possible, as the third example illustrates.
Proof. Let \(v\) be any vertex in a disconnected graph. There is at least one other component, so choose a vertex \(w\) in that component. No path joins \(v\) to \(w\), and therefore \(d(v,w)=\infty\). The eccentricity of \(v\) is the maximum of its distances to all vertices, so \(\operatorname{ecc}(v)=\infty\). This holds for every vertex \(v\). The minimum and maximum of the resulting eccentricities are both \(\infty\), giving global radius and diameter \(\infty\). \(\square\)
This convention makes disconnectedness explicit, but it also explains why a componentwise report is often more informative. Calculate distances only between vertices in the same component, and state which component each radius, diameter, or center belongs to. Do not silently treat unreachable vertices as if they were simply absent from a global calculation.
Common Pitfall
Ignoring unreachable vertices changes the question. In the second example, one might calculate distances from vertex \(7\), see only \(d(7,7)=0\), and report that its global eccentricity is \(0\). That calculation has omitted vertices \(1\) through \(6\), which are unreachable from \(7\). The global eccentricity is \(\infty\), while the eccentricity of \(7\) within its own one-vertex component is \(0\). Both statements are correct, but they refer to different summaries. Always say whether the distances and eccentricities are global or componentwise.
Also distinguish a path you have found from proof that it is shortest. A path of length \(k\) shows that distance is at most \(k\); the layer calculation, or a complete distance table, is what confirms that no shorter path exists.
Check Your Understanding
For each question, specify whether you are using global or componentwise distances whenever the graph is disconnected.
- For the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), write the distance table and identify its center and peripheral vertices.
- For the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23\}\), find the components. What is the global eccentricity of vertex \(4\), and what is its componentwise eccentricity?
- In a connected graph, explain why a vertex first appearing in layer \(L_k\) has distance exactly \(k\) from the starting vertex.
- For the graph with \(V=\{p,q,r,s\}\) and \(E=\{pq,qr,rs,sp\}\), build a distance table and find all central vertices.
- A path of length \(5\) joins two vertices. What does this establish about their distance, and what additional information would establish that the path is shortest?