In this section, we will prove that no matter how an adversary selects
*f* switches to be faulty, there are always at least inputs
and outputs through which any permutation on those inputs and
outputs can be routed in steps. In fact, the greedy
algorithm described in Section 2 works once we have
removed an appropriate set of switches which include at most
inputs and outputs.

We first describe which outputs to remove. Examine each splitter in the multibutterfly and check if more than an fraction of the input switches are faulty, where and . If so, then ``erase'' the splitter from the network as well as all descendant switches and outputs. The following lemma bounds the number of erased outputs.

**Proof:**
The erasure of an *M*-input splitter causes the removal of
*M* multibutterfly outputs, and accounts for at least
faults. Hence, at most multibutterfly outputs are removed by this process.

to .667emto .667em

We next describe which inputs to remove. Working from level backwards, examine each switch to see if at least half of its upper output edges lead to faulty switches that have not been erased, or if at least half of its lower output edges lead to faulty switches that have not been erased. If so, then declare the switch to be faulty (but do not erase it). In the following lemmas, we will prove that at most additional switches are declared to be faulty at each level of this process. Hence, at most multibutterfly inputs will be faulty (declared or otherwise).

**Proof:**
The proof is by induction on the level, starting at level
and working backwards. The base case at level is
trivial since there are no propagated faults on level . Now
consider an arbitrary *M*-input splitter on level *i*. Let
denote the set of faults propagated from the splitter's upper outputs
and let denote those propagated from the lower outputs. If the
upper outputs were erased, then . Otherwise, the
number of faults placed by the adversary in the upper outputs is at
most . Since each propagated input fault is
connected to at most working upper
outputs, we can conclude that . By induction, and . For
and , we have a contradiction. A
similar argument shows that .

to .667emto .667em

**Proof:**
The proof is again by induction on the level. Consider some
level *l* and assume that it has more than
propagated faults. By Lemma 3.2, we know that these
faults are divided among the splitters linking level *l* to *l+1* so
that we can apply the expansion property to the faults within each
splitter. Hence there must be more than
faults on level
*l+1*. This is a contradiction however, since level *l+1* can have at
most total faults by induction. Hence, level *l*
can have at most propagated faults.

to .667emto .667em

We now erase all the remaining faulty switches. This leaves a network with inputs and outputs. Moreover, every input in every splitter is linked to functioning upper outputs (if the descendant multibutterfly outputs exist) and functioning lower outputs (if the corresponding multibutterfly outputs exist). Hence every splitter has an expansion property. Thus, we can apply Theorem 2.1 with replaced by to prove that the greedy algorithm still routes any permutation on the remaining inputs and outputs in steps. This is summarized as Theorem 3.4 below. (Note that we can achieve expansion for .)

**Proof:**
The results follows from Theorem 2.1,
Lemmas 3.1 and 3.3, and the fact that
.

to .667emto .667em

Mon Jul 22 18:45:42 EDT 1996