Graph which do not satisfy a pseudo-Poincaré inequality Say that an infinite (connected) graph (with vertices of bounded degree) satisfies a $\ell_1$-pseudo-Poincaré inequality if there is a constant $C>0$ so that for any $n \in  \mathbb{N}$ for any function $f \in \ell_1(V)$ on the vertices of the graph
$$
\| f - f_n \|_{\ell_1(V)} \leq C \cdot n \cdot \|\nabla f\|_{\ell_1(E)}
$$
where


*

*$f_n$ is the function defined by: $f_n(x)$ is the average of the values of $f$ over a ball of radius $n$ centered at $x$, or $f_n(x) = \displaystyle \frac{1}{|B_n(x)|} \sum_{y \in B_n(x)} f(y)$ where $B_n(x)$ denotes the ball of radius $n$ around $x$.

*$\nabla f$ is the function on the edges which associate to the edge $(x,y) \in E$ between the vertices $x$ and $y$ the value $f(x) - f(y)$. [It's not important whether on consider edges oriented or not or to be present once with each orientation; at worst, it changes the constant by a factor of 2.]

*$\|g\|_{\ell_1}$ are the $\ell_1$-norms : for functiond defined on the vertices its $\|g\|_{\ell_1(V)} = \displaystyle \sum_{x \in V} |g(x)|$ and for function defined on the edges its $\|g\|_{\ell_1(E)} = \displaystyle \sum_{(x,y) \in E} |g(x,y)|$
I'm pretty sure there are graphs which do not satisfy this inequality, but I could not find any reference. So
Question: what are examples of graph which do not satisfy this inequality?
It's known that Cayley graphs satisfy this pseudo-Poincaré inequality. I would be particularly interested in a counterexample which is a subgraph of a Cayley graph (since I my guess would be that this inequality does not pass to subgraphs). A counterexample which is a tree would do the trick.
[Addendum 1]
This $\ell_1$-pseudo-Poincar\'e inequality is used in groups to show an isoperimetric inequality: 
Let $\phi(\lambda) = \inf \{ n \mid |B_n| \geq \lambda\}$. Then
$
\frac{ |A|}{\phi(2|A|)} \leq 2C |\partial A|
$
See Coulhon & Saloff-Coste Isopérimétrie pour les groupes et les variétés, Revista Matemática Iberoamericana 9(2):293--314, 1993. I believe there is a survey from Pittet & Saloff-Coste which contain these proofs and is written in English.
When balls are not isomorphic, I believe one must replace $|B_n|$ by $b_n = \displaystyle \inf_{x \in V} |B_n(x)|$.
[Addendum 2]
This is how the inequality is proved in case of Cayley graphs (also from Coulhon & Saloff-Coste). 
Statement:
Let $G$ be a group and consider the Cayley graph for the generating set $S$.
For any $f \in \ell^1$ (in particular of finite support), $\|f-f_{n}\|_1 \leq n \|\nabla f\|_1$
Proof:
First write $f*\delta_y$ for the function $(f*\delta_y)(x) = f(xy)$ (this is the convolution with a Dirac funtion).
Note that $\|f - f * \delta_y\|_1 \leq \| \nabla f\|_1$ if $y$ is in $S$. If $y \in B_n$, then apply the triangle inequality: write $y = s_1 \ldots s_n$ with $s_i \in S$ and
$$
\begin{array}{rl}
\|f - f * \delta_y\|_1
&\displaystyle \leq \| \sum_{i = 1}^n f * \delta_{s_1 \ldots s_{i-1}} - f * \delta_{s_1 \ldots s_i} \|_1 \\
&\displaystyle \overset{\text{T.I.}}\leq  \sum_{i = 1}^n \|f(\cdot  s_1 \ldots s_{i-1}) - f(\cdot  s_1 \ldots s_i) \|_1 \\
&\displaystyle \leq n \|\nabla f\|_1 
\end{array}
$$
and then
$$
\begin{array}{rll}
\|f - f_n\|_1 
&= \displaystyle \| f - \tfrac{1}{|B_n|} \sum_{y \in B_n }f* \delta_y \|_1 
&= \displaystyle \| \tfrac{1}{|B_n|} \sum_{y \in B_n } f - f* \delta_y \|_1 \\
& \displaystyle  \overset{\text{T.I.}}\leq  \tfrac{1}{|B_n|} \sum_{y \in B_n } \|f - f* \delta_y \|_1 
& \leq n \|\nabla f\|_1.
\end{array}
$$
This concludes the proof.
 A: A counterexample is the subgraph of the $\mathbb{Z}^2$ Cayley graph found by taking squares $S_i$ of side $i$ and arranging them along a (near)diagonal in a chain so that each $S_i$ is adjacent to $S_{i+1}$ along a single edge, and no other edges connect any $S_i$ to any other.
Suppose the given inequality held.  For a given $n$, choose $i > 10n$ and let $f$ be the characteristic function of $S_i$.  Then the right hand side of the inequality is $\sim C n \cdot 2$.  On the other hand, for each of the $\sim n^2$ points within distance $n/2$ of the edge between $S_i$ and $S_{i+1}$ we have that $f_n$ is bounded away from $0$ and $1$, and so the left hand side of the inequality is $\gtrsim n^2$.
A: Why I do not have a relevant counterexample yet, I decided to write an extended comment on related Poincaré and Sobolev inequalities. The purpose was to place the question in the right context, provide a source that contains many related references and mention a result (inequality (*)) in the positive direction that is strictly related to the inequality in the question.
A lot is known about Poincaré inequalities on Cayley graphs of finitely generated groups of polynomial growth.
Denote by $|B|$ volume (number of points) in a of a ball $B$. Denote also by $f_B$ average of $f$ on $B$. Also $|\nabla f(x)|=\sum_{y\sim x}|f(x)-f(y)|$ where $x\sim y$ mean that $x$ and $y$ are connected by an edge.

Theorem. If $G$ is a finitely generated group of polynomial growth i.e. volume of a ball of radius $n$ in the associated Caley graph is
  $\approx n^d$ for some positive integer $d$. Then for any ball $B$ of
  radius $n$ the following Sobolev-Poincare inequality is true: $$
 \left(\frac{1}{|B|}\sum_{x\in B}|f(x)-f_B|^q\right)^{1/q}\leq C n 
 \left(\frac{1}{|B|}\sum_{x\in B}|\nabla f(x)|^p\right)^{1/p} $$ where
  $1\leq p<d$ and $1\leq q\leq dp/(d-p)$. The constant $C$ does not depend on $B$.

In particular taking $p=q=1$ yields
$$
\sum_{x\in B}|f(x)-f_B|\leq C n 
 \sum_{x\in B}|\nabla f(x)|
\qquad\qquad (*)
$$
This is similar to your inequality but the difference is that you take the $\ell^1$ norm on the ball and not on the whole graph. Also the graph cannot be arbitrary. You need some structure in order to prove the Poincaré inequality. 
For a proof of the above result and many references see:
P. Hajłasz, P. Koskela, Sobolev met Poincaré.  Mem. Amer. Math. Soc. 145 (2000), no. 688.
