Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability $p$, independently of each other, and a deterministic spreading rule with a fixed parameter $k$: if a vacant site has at least $k$ occupied neighbours at a certain time step, then it becomes occupied in the next step. This process is well studied on ${\mathbb Z}^d$; here we investigate it on regular and general infinite trees and on non-amenable Cayley graphs. The critical probability is the infimum of those values of $p$ for which the process achieves complete occupation with positive probability. On trees we find the following discontinuity: if the branching number of a tree is strictly smaller than $k$, then the critical probability is 1, while it is $1-1/k$ on the $k$-ary tree. A related result is that in any rooted tree $T$ there is a way of erasing $k$ children of the root, together with all their descendants, and repeating this for all remaining children, and so on, such that the remaining tree $T'$ has branching number $\mbox{\rm br}(T')\leq \max\{\mbox{\rm br}(T)-k,\,0\}$. We also prove that on any $2k$-regular non-amenable graph, the critical probability for the $k$-rule is strictly positive.