Let $G = (V,E)$ be an undirected connected graph. Suppose $G$ has a pair of nodes $s,t$ that are distance $d$ apart. Show that there is a vertex $v\in G$ such that the degree of $v$ is at most $6n/d$ where $n = |V|$.
Show that for directed graphs the above is not true. More precisely, give an example of a directed graph on $n$ nodes such that there is a pair of nodes $s, t$ such that distance from $s$ to $t$ is $\Omega(n)$ and for each node $v$ in the graph, both the in-degree and out-degree are $\Omega(n)$.
