Reliable electroencephalography (EEG) signatures of transitions between consciousness and unconsciousness under anaesthesia have not yet been identified. Herein we examined network changes using graph theoretical analysis of high-density EEG during patient-titrated propofol-induced sedation. Responsiveness was used as a surrogate for consciousness. We divided the data into five states: baseline, transition into unresponsiveness, unresponsiveness, transition into responsiveness, and recovery. Power spectral analysis showed that delta power increased from responsiveness to unresponsiveness. In unresponsiveness, delta waves propagated from frontal to parietal regions as a traveling wave. Local increases in delta connectivity were evident in parietal but not frontal regions. Graph theory analysis showed that increased local efficiency could differentiate the levels of responsiveness. Interestingly, during transitions of responsive states, increased beta connectivity was noted relative to consciousness and unconsciousness, again with increased local efficiency. Abrupt network changes are evident in the transitions in responsiveness, with increased beta band power/connectivity marking transitions between responsive states, while the delta power/connectivity changes were consistent with the fading of consciousness using its surrogate responsiveness. These results provide novel insights into the neural correlates of these behavioural transitions and EEG signatures for monitoring the levels of consciousness under sedation.