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.
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 
.
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.
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
.
