On cycling in the network simplex method

There are well-known examples of cycling in the linear programming simplex method having basis size two and requiring only six pivots. We prove that any example having basis size two for the network simplex method requires at least ten pivots. We also present an example that achieves this lower bound. In addition, we show that an attractive variant of Cunningham's noncyling method does admit cycling.