  Markov Chain Monte Carlo (MCMC) algorithms are commonly used to sample from
graph ensembles. Two graphs are neighbors in the state space if one can be
obtained from the other with only a few modifications, e.g., edge rewirings.
For many common ensembles, e.g., those preserving the degree sequences of
bipartite graphs, rewiring operations involving two edges are sufficient to
create a fully-connected state space, and they can be performed efficiently. We
show that, for ensembles of bipartite graphs with fixed degree sequences and
number of butterflies (k2,2 bi-cliques), there is no universal constant c such
that a rewiring of at most c edges at every step is sufficient for any such
ensemble to be fully connected. Our proof relies on an explicit construction of
a family of pairs of graphs with the same degree sequences and number of
butterflies, with each pair indexed by a natural c, and such that any sequence
of rewiring operations transforming one graph into the other must include at
least one rewiring operation involving at least c edges. Whether rewiring these
many edges is sufficient to guarantee the full connectivity of the state space
of any such ensemble remains an open question. Our result implies the
impossibility of developing efficient, graph-agnostic, MCMC algorithms for
these ensembles, as the necessity to rewire an impractically large number of
edges may hinder taking a step on the state space.
