Flow on Infinite Graphs Assume you have a simple, infinite graph $G$ with bounded degree (there is an upper bound for the degree of the nodes). Choose an arbitrary vertex $x\in V(G)$ and consider 
$$
G_{n}:=\{x\in G:d(x_0,x)\leq n\}
$$
with the graph metric (hop metric). Assume that each pair of nodes is communicating a unit load of information and the load goes through the minimum path between nodes (if there is more than one minimum path we choose one arbitrarily). The total traffic in $G_{n}$ is equal to $\frac{N(N-1)}{2}$ where $N=N(n)=|G_{n}|$.
Given a node $v\in G_{n}$ we define $T_{n}(v)$ as the total traffic generated in $G_{n}$ passing through $v$. In other words, $T_{n}(v)$ is the sum off all the geodesic paths in $G_{n}$ which are carrying traffic and contain the node $v$.
If the graph $G$ is planar and it has exponential growth $|G_{n}|=K\exp(\lambda n)$ for $n$ sufficiently large, then it is not difficult to prove that there are nodes in $G_{n}$ such that 
$$
T_{n}(v)\geq C\frac{N^2}{\log(N)}
$$
for $n$ sufficiently large.
My question is the following

Is the same true if we remove the
  planar condition but we keep the
  exponential growth? My intuition is
  that the answer is no but I can't find
  a counterexample.

 A: I think the following provides a counterexample.
The idea is to use the fact that on a graph $G$ with maximum degree $\Delta$ and diameter $D$  reasonably close to the natural lower bound $\log_{\Delta-1}|V(G)|$ the traffic is almost uniformly distributed.
Explicitly, for a vertex $v$, let $S_k(v):=\{x \in V(G) \: | \: d(x,v)=k\}$. Then $|S_k(v)| \leq \Delta(\Delta-1)^{k-1}$ and the traffic through $v$ can be estimated as $$T_G(v) \leq \sum_{k+l \leq D} |S_k(v)||S_l(v)| < D^2\Delta^2(\Delta-1)^{D-2}.$$
Bollobas and de la Vega in a paper "The diameter of random regular graphs" (last reference for Lecture 1 at the link.) show that for sufficiently large $N'$ a random $r$-regular graph on $N'$ vertices has diameter at most $\log_{r-1}(N') + \log_{r-1}(\log_{r-1}(N'))+C$, where $C$ is a (small) constant depending on $r$. By adjusting $C$, we may assume that an $r$-regular graph on $N'$ vertices satisfying this bound on diameter exists for any $N'$.
Finally, we construct $G$ by, first, taking an infinite $r$-regular tree, except that for simplicity of calculations we let the degree of $x_0$ be $r-1$. Secondly, we put an $r$-regular graph with the diameter bound listed above on the set of vertices $S_k(x_0)$, that is on each level of our infinite tree, considered as rooted at $x_0$. 
Note that $|S_k(x_0)|=(r-1)^k$ and the diameter of $G|S_k(x_0)$ (i.e. $G$ restricted to $S_k(x_0)$) is at most $k + \log_{r-1}(k)+C$. It follows that the diameter of $G_n$ is at most $$\max_{k \leq l \leq n}( \mathrm{diam}(G|S_k(x_0)) + l-k) \leq n + \log_{r-1}(n)+C$$
The graph $G_n$ has maximum degree $\Delta = 2r$ and by the bound on the traffic load above we have
$$ T_n(v) \leq n^2(2r-1)^{n+\log_{r-1}(n)+C'}$$
for any $v \in V(G_n)$ and some choice of $C'(r)$ independent on $n$.
On the other hand $$|V(G_n)|=N =\sum_{k=0}^n (r-1)^k > (r-1)^n$$ 
It follows that, for any $\epsilon >0$ we can choose large enough $r$ so that for large $n$ we have $T_n(v) \leq N^{1 + \epsilon}$ for every $v \in G_n$.
