Disconnection Numbers, Pizza Cuts, and Cycle Rank

Abstract

In this paper we bring out more strongly the connection between the disconnection number of a graph and its cycle rank. We also show how to associate with a pizza sliced right across in a certain way with $n-2$ cuts a graph with $n$ vertices, and show that if the pizza is cut thereby into $r$ pieces, then any set of $r-1$ of these pieces corresponds to a basis for the cycle space of the associated graph. Finally we use this to explain why for $n\ge 3$ the greatest number of regions that can be formed by slicing a pizza in the certain way with $n-2$ cuts, namely $\frac{1}{2}(n^2-3n+4)$, equals the disconnection number of $K_n$.