  We consider the connectivity of fiber graphs with respect to Gr\"obner basis
and Graver basis moves. First, we present a sequence of fiber graphs using
moves from a Gr\"obner basis and prove that their edge-connectivity is lowest
possible and can have an arbitrarily large distance from the minimal degree. We
then show that graph-theoretic properties of fiber graphs do not depend on the
size of the right-hand side. This provides a counterexample to a conjecture of
Engstr\"om on the node-connectivity of fiber graphs. Our main result shows that
the edge-connectivity in all fiber graphs of this counterexample is best
possible if we use moves from Graver basis instead.
