What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?
Diameter of a graph with O(|V|) edges
graph theory;co.combinatorics
A line graph has O(V) edges and diameter V-1. A star graph also has O(V) edges and diameter 2. So it seems that the constraint that a graph has O(V) edges places almost no restriction at all on what the diameter can be. Of course, 2 is the minimum, since only a complete graph has diameter 1. 