[31] Prove the following: For shortest-path routing on c log nrandom graphs, if nodes know their neighbors and nodes may be relabeled by arbitrary identifiers (which therefore can code information), then with labels of size at most (1 + (c + 3) log n) log n bits the local routing functions can be stored in O(1) bits per node. Hence the complete routing scheme including the label information is represented by

(c + 3)n log2 n + n log n + O(n) bits.