2. (20 pt) A number of stories in the press about the structure of the Internet and the Web have focused on some version of the following question: How far apart are typical nodes in these networks? If you read these stories carefully, you nd that many of them are confused about the difference between the diameter of a network and the average distance in a network; they often jump back and forth between these concepts as though they're the same thing. As in the text, we say that the distance between two nodes u and v in a graph G = (V, E) is the minimum number of edges in a path joining them; we'll denote this by dist(u,v). We say that the diameter of G is the maximum distance between any pair of nodes; and we'll denote this quantity by diam(G). Let's dene a related quantity, which we'll call the average pairwise distance in G (denoted apd(G)). We define apd (G) to be the average, over all (2) sets of two distinct nodes u and v, of the distance between u and v. That is, apd(G)= Z dist(u,v) /('2'). {u,v}V Here's a simple example to convince yourself that there are graphs G for which diam(G) 75 apd (G). Let G be a graph with three nodes u, v, w, and with the two edges {11, v} and {v, w}. Then diam(G) = dist(u, w) = 2, while apd(G) = [dist(u,v) + dist(u, w) + dist(v, w)]/3 = 4/3. Of course, these two numbers aren't all that far apart in the case of this three-node graph, and so it's natural to ask whether there's always a close relation between them. Here's a claim that tries to make this precise. Claim: There exists a positive natural number c so that for all connected undirected graphs G (with arbitrary number of nodes), it is the case that diam(G) S c. apd(G) Decide whether you think the claim is true of false, and give a proof of either the claim or its negation