  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 neighbors at a certain time step, then it
becomes occupied in the next step. This process is well-studied on 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 general
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 \br(T') \leq \max (\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.
