  Let $p$ be a real number greater than one and let $G$ be a connected graph of
bounded degree. In this paper we introduce the $p$-harmonic boundary of $G$. We
use this boundary to characterize the graphs $G$ for which the constant
functions are the only $p$-harmonic functions on $G$. It is shown that any
continuous function on the $p$-harmonic boundary of $G$ can be extended to a
function that is $p$-harmonic on $G$. Some properties of this boundary that are
preserved under rough-isometries are also given. Now let $\Gamma$ be a finitely
generated group. As an application of our results we characterize the vanishing
of the first reduced $\ell^p$-cohomology of $\Gamma$ in terms of the
cardinality of its $p$-harmonic boundary. We also study the relationship
between translation invariant linear functionals on a certain difference space
of functions on $\Gamma$, the $p$-harmonic boundary of $\Gamma$ with the first
reduced $\ell^p$-cohomology of $\Gamma$.
