Segmentation of medical images has become an indispensable process to perform quantitative analysis of images of human organs and their functions. Normalized Cuts (NCut) is a spectral graph theoretic method that readily admits combinations of different features for image segmentation. The computational demand imposed by NCut has been successfully alleviated with the Nyström approximation method for applications different than medical imaging. In this paper we discuss the application of NCut with the Nyström approximation method to segment vertebral bodies from sagittal T1-weighted magnetic resonance images of the spine. The magnetic resonance images were preprocessed by the anisotropic diffusion algorithm, and three-dimensional local histograms of brightness was chosen as the segmentation feature. Results of the segmentation as well as limitations and challenges in this area are presented.