Let p be a real number
greater than one and let G be a connected graph of bounded degree. We introduce
the p-harmonic boundary of G and use it to characterize the graphs G for which the
constant functions are the only p-harmonic functions on G. We show that any
continuous function on the p-harmonic boundary of G can be extended to
a function that is p-harmonic on G. We also give some properties of this
boundary that are preserved under rough-isometries. Now let Γ be a finitely
generated group. As an application of our results, we characterize the vanishing
of the first reduced ℓp-cohomology of Γ 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
Γ, the p-harmonic boundary of Γ, and the first reduced ℓp-cohomology of
Γ.