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 Gamma be a finitely generated group. As an application of our results, we characterize the vanishing of the first reduced lp-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, and the first reduced lp-cohomology of Gamma.