The volume operator is an important kinematical quantity in the non-pe
rturbative approach to four-dimensional quantum gravity in the connect
ion formulation. We give a general algorithm for computing its spectru
m when acting on four-valent spin network states, evaluate some of the
eigenvalue formulae explicitly, and discuss the role played by the Ma
ndelstam constraints.