Whether unique to humans or not, consciousness is a central aspect of our experience of the world. The neural fingerprint of this experience, however, remains one of the least understood aspects of the human brain. In this paper we employ graph-theoretic measures and support vector machine classification to assess, in 12 healthy volunteers, the dynamic reconfiguration of functional connectivity during wakefulness, propofol-induced sedation and loss of consciousness, and the recovery of wakefulness. Our main findings, based on resting-state fMRI, are three-fold. First, we find that propofol-induced anesthesia does not bear differently on long-range versus short-range connections. Second, our multi-stage design dissociated an initial phase of thalamo-cortical and cortico-cortical hyperconnectivity, present during sedation, from a phase of cortico-cortical hypoconnectivity, apparent during loss of consciousness. Finally, we show that while clustering is increased during loss of consciousness, as recently suggested, it also remains significantly elevated during wakefulness recovery. Conversely, the characteristic path length of brain networks (i.e., the average functional distance between any two regions of the brain) appears significantly increased only during loss of consciousness, marking a decrease of global information-processing efficiency uniquely associated with unconsciousness. These findings suggest that propofol-induced loss of consciousness is mainly tied to cortico-cortical and not thalamo-cortical mechanisms, and that decreased efficiency of information flow is the main feature differentiating the conscious from the unconscious brain.