Network Structures

1. The length of a path in a simple graph is the number of edges on it. The distance between two nodes of a simple graph is the length of the shortest path connecting them. The diameter of a graph is the maximum distance between a pair of nodes. Let ₁ , . . . , be all the nodes of a graph G, and let dist_G(, ) be the distance between and in this graph G. Then the average distance between nodes of G is the number

distG(vi, 'j) Notice that there are (2) pairs of nodes vi and Uj such that l 1 . What is the diameter of this graph? graphs is less than 2 graph whose diameter is greater than and the average distance between nodes average distance betw (b) Generalize the example of (a) to show that for any integer > 0 there exists a is less than 2