The algorithm of Section 3.3 augments
the multibutterfly network with two types of edges. First 
edges
are added from each switch to switches in the same block. Then
edges are added from each switch to both the upper and lower
blocks at the next level. The second type of edges are easily
removed. Their tasks can be performed by the d routing edges
leading from each switch to the upper and lower blocks at the next level.
Removing the first type of edges is more problematic. The basic idea
is to simulate them using the d routing edges. We begin by
observing that a randomly-wired splitter is likely to have expansion
both from the inputs to the outputs and from the outputs to the inputs
[7, 12]. Let 
be the
expansion property from the output blocks (taken together) to their
input block. Then 
, and 
will be close
to 2d-1, provided that 
is sufficiently small. A set of
input switches in a block of size M has at least
output neighbors (counting those in both the upper and
lower blocks). These outputs in turn have at least 
input neighbors, provided 
. Thus, as
long as none of the output neighbors are faulty, they can be used to
simulate expansion 
within the block. This expansion can be used in place
of 
in the algorithm of
Section 3.3. What if some of these
output neighbors are faulty? This problem can be solved by declaring a
switch to be faulty if any of its output neighbors are faulty
(without propagating any faults) before the reconfiguration
process begins. This trick may multiply the number of faults in the
network by a factor of 2d, but if a switch survives then all of its
output neighbors were initially working.