Our circuit-switching algorithm requires the splitters in the multibutterfly to have a special ``unshared-neighbors'' property defined as follows.
By Equation 2.1, we know that randomly-generated splitters have the unshared-neighbors property where approaches 1 as d gets large and gets small. Explicit constructions of such splitters are not known, however. Nevertheless, we will consider only multibutterflies with the unshared-neighbors property for in what follows.
Remark: The expansion property ( ) is a sufficient condition for the unshared-neighbors property, but by no means necessary. In fact, we can easily prove the existence of random splitters which have a fairly strong unshared-neighbors property for small degree. For such graphs, the routing algorithm we are about to describe is more efficient in terms of hardware required. However, multibutterflies with expansion properties will remain the object of our focus.