$30
CS180 Homework 2
Please submit your homework on gradescope. No late submission is allowed.
1. (20 pt) Prove or disprove the following statement:
For a graph G with n nodes (n is even), if every node of G has degree at least n/2, then G is connected.
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 find 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 dis t(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 define 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
n
2
sets of two distinct nodes u and v, of the distance between u
and v. That is,
apd(G) =
X
{u,v}⊆V
dis t(u, v)
/
n
2
.
Here’s a simple example to convince yourself that there are graphs G for which diam(G) 6= apd(G). Let G
be a graph with three nodes u, v, w, and with the two edges {u, v} and {v, w}. Then
diam(G) = dis t(u, w) = 2,
while
apd(G) = [dis t(u, v) + dis t(u, w) + dis t(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)
apd(G)
≤ c.
Decide whether you think the claim is true of false, and give a proof of either the claim or its negation.
3. We have defined the diameter of a graph in Problem 2. Finding the diameter of a graph is not an easy
problem on a general graph, but we consider a special case when G is a tree:
(a) (20 pt) Assume G is a tree (undirected, connected graph without any cycle). Assume we are given
a function A(·) such that given an input u, it will return a node v that maximizes dist(u, v) and the
corresponding distance. There exists an algorithm that can compute the diameter of a tree using a
constant calls of the function A without using any other graph traversal algorithms (e.g., BFS/DFS).
Try to design such algorithm and prove the correctness of your algorithm.
(b) (5 pt) Which graph traversal algorithm we introduced in the class can be used for implementing the
function A? And what will be the overall time complexity for this diameter computing algorithm for
trees in part (a)