Graph theoretical analysis of functional magnetic resonance imaging (fMRI) time series has revealed a small-world organization of slow-frequency blood oxygen level-dependent (BOLD) signal fluctuations during wakeful resting. In this study, we used graph theoretical measures to explore how physiological changes during sleep are reflected in functional connectivity and small-world network properties of a large-scale, low-frequency functional brain network. Twenty-five young and healthy participants fell asleep during a 26.7 min fMRI scan with simultaneous polysomnography. A maximum overlap discrete wavelet transformation was applied to fMRI time series extracted from 90 cortical and subcortical regions in normalized space after residualization of the raw signal against unspecific sources of signal fluctuations; functional connectivity analysis focused on the slow-frequency BOLD signal fluctuations between 0.03 and 0.06 Hz. We observed that in the transition from wakefulness to light sleep, thalamocortical connectivity was sharply reduced, whereas corticocortical connectivity increased; corticocortical connectivity subsequently broke down in slow-wave sleep. Local clustering values were closest to random values in light sleep, whereas slow-wave sleep was characterized by the highest clustering ratio (gamma). Our findings support the hypothesis that changes in consciousness in the descent to sleep are subserved by reduced thalamocortical connectivity at sleep onset and a breakdown of general connectivity in slow-wave sleep, with both processes limiting the capacity of the brain to integrate information across functional modules.