[Cs4800] Hint for the diameter-apd problem

[Karl Lieberherr]

For the graph problem:
Let's assume that your combined graph G has  n nodes total
of which k-1 nodes are
on the line graph. It pays to only compute an upper bound for
apd(G). For example, when you calculate the apd contribution
of the star graph only you might as well count all (n choose 2)
pairs each having a distance of at most two. This overcounts
but not by too much and it simplifies the computation.

You may use another graph than the star graph but it is probably
easier with the star graph.