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.
> 
> 
> 



Flow on Infinite Graphs
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](http://www.stanford.edu/class/msande337/)" (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$.


