When we think about a single aggregate measure to summarize the distances between the nodes in a…
When we think about a single aggregate measure to summarize the distances between the nodes in a given graph, two natural quantities come to mind. One is the diameter, which we define to be the maximum distance between any pair of nodes in the graph. Another is the average distance, which, as the term suggests, is the average distance over all pairs of nodes in the graph.
In many graphs, these two quantities are close to each other in value. But there are graphs where they can be very different.
(a) Describe an example of a graph where the diameter is more than three times as large as the average distance.
(b) Describe how you could extend your construction to produce graphs in which the diameter exceeds the average distance by as large a factor as you would like. (That is, for every number c, can you produce a graph in which the diameter is more than c times as large as the average distance?)