# 1 let the diameter of a graph be dened to denote the maximum distance between any pa 5346686

1. Let the diameter of a graph be dened to denote the maximum distance between any

pair of nodes. The average distance of a graph is the average distance of a pair of

nodes counted over all pairs of nodes.

(a) Describe an example of a graph where the diameter is more than three times as

large as the average distance.

(b) Describe a construction of examples of graphs Gk, for any integer k > 1, in which

the diameter is more than k times the average distance.

2. Apply the Girvan-Newman method to a graph which is a simple path of seven edges.

Describe the process how the graph is partitioned into separate nodes.

3. Given a bipartite affiliation graph that shows the membership of people in dierent

social foci, the corresponding projected graph has just people as the nodes, with two

nodes connected when they have a focus in common. Give an example of two dierent

affiliation networks – on the same set of people, but with dierent foci – so that the

projected graphs from these two dierent affiliation networks are the same.

4. There are 50 farms along a 50-mile-long stretch of a river. Each farmer lives on a tract

of land that occupies a 1-mile stretch of the river bank, so their tracts exactly divide

up the 50 miles of river bank they collectively cover. The farmers all know each other.

Each farmer is friends with all the other farmers that live at most 20 miles from him

or her, and are enemies with all the farmers that live more than 20 miles from him or

her. Consider the signed complete graph corresponding to this social network. Is the

network structurally balanced or not?