Recent advances in functional neuroimaging have demonstrated novel potential for informing diagnosis and prognosis in the unresponsive wakeful syndrome and minimally conscious states. However, these technologies come with considerable expense and difficulty, limiting the possibility of wider clinical application in patients. Here, we show that high density electroencephalography, collected from 104 patients measured at rest, can provide valuable information about brain connectivity that correlates with behaviour and functional neuroimaging. Using graph theory, we visualize and quantify spectral connectivity estimated from electroencephalography as a dense brain network. Our findings demonstrate that key quantitative metrics of these networks correlate with the continuum of behavioural recovery in patients, ranging from those diagnosed as unresponsive, through those who have emerged from minimally conscious, to the fully conscious locked-in syndrome. In particular, a network metric indexing the presence of densely interconnected central hubs of connectivity discriminated behavioural consciousness with accuracy comparable to that achieved by expert assessment with positron emission tomography. We also show that this metric correlates strongly with brain metabolism. Further, with classification analysis, we predict the behavioural diagnosis, brain metabolism and 1-year clinical outcome of individual patients. Finally, we demonstrate that assessments of brain networks show robust connectivity in patients diagnosed as unresponsive by clinical consensus, but later rediagnosed as minimally conscious with the Coma Recovery Scale-Revised. Classification analysis of their brain network identified each of these misdiagnosed patients as minimally conscious, corroborating their behavioural diagnoses. If deployed at the bedside in the clinical context, such network measurements could complement systematic behavioural assessment and help reduce the high misdiagnosis rate reported in these patients. These metrics could also identify patients in whom further assessment is warranted using neuroimaging or conventional clinical evaluation. Finally, by providing objective characterization of states of consciousness, repeated assessments of network metrics could help track individual patients longitudinally, and also assess their neural responses to therapeutic and pharmacological interventions.