Diameter (graph theory)

In graph theory, the diameter of a graph is the greatest distance between any two vertices in the graph. This distance is measured by the length of the shortest path between those vertices. In other words, the diameter is the maximum eccentricity of any vertex in the graph.

More formally:

1. The distance between two vertices u and v in a graph G, denoted d(u, v), is the length (number of edges) of the shortest path connecting u and v. If no path exists between u and v, then d(u, v) = ∞.

2. The eccentricity of a vertex v in a graph G, denoted ecc(v), is the greatest distance from v to any other vertex in G. Thus, ecc(v) = max{d(v, u) | u ∈ V(G)}, where V(G) is the set of vertices in G.

3. The diameter of a graph G, denoted diam(G), is the maximum eccentricity of any vertex in the graph. Thus, diam(G) = max{ecc(v) | v ∈ V(G)}. Equivalently, the diameter of a graph is the maximum shortest path length between any two vertices in the graph: diam(G) = max{d(u, v) | u, v ∈ V(G)}.

For disconnected graphs, where some pairs of vertices have no path connecting them, the distance between such vertices is defined to be infinite. Therefore, the diameter of a disconnected graph is also infinite.

For a graph with only one vertex, the diameter is typically defined as 0.