If any large tree in the input block counts more than
switches that are awake in an
output block of size then it *marks* all of those
switches. As we shall see, a block will be erased unless it contains
a marked switch, in which case it will not be erased. The following
lemma bounds the number of network outputs that are erased.

**Proof:**
If an output block of size has fewer than
faults, then by Lemma 3.3, after steps it will
have at most faulty and asleep switches.
Since the switches in each large tree have at least
neighbors in each output block, at
least of those neighbors must be
awake. These neighbors will all be marked and the block will not be
erased. Thus, if an output block is erased, then it must have had at
least an fraction of faulty switches to begin with.

to .667emto .667em

Mon Jul 22 19:56:03 EDT 1996