Cognitive dysfunction in Multiple Sclerosis (MS) is closely related to altered functional brain network topology. Conventional network analyses to compare groups are hampered by differences in network size, density and suffer from normalization problems. We therefore computed the Minimum Spanning Tree (MST), a sub-graph of the original network, to counter these problems. We hypothesize that functional network changes analysed with MSTs are important for understanding cognitive changes in MS and that changes in MST topology also represent changes in the critical backbone of the original brain networks. Here, resting-state magnetoencephalography (MEG) recordings from 21 early MS patients and 17 age-, gender-, and education-matched controls were projected onto atlas-based regions-of-interest (ROIs) using beamforming. The phase lag index was applied to compute functional connectivity between regions, from which a graph and subsequently the MST was constructed. Results showed lower global integration in the alpha2 (10-13. Hz) and beta (13-30. Hz) bands in MS patients, whereas higher global integration was found in the theta band. Changes were most pronounced in the alpha2 band where a loss of hierarchical structure was observed, which was associated with poorer cognitive performance. Finally, the MST in MS patients as well as in healthy controls may represent the critical backbone of the original network. Together, these findings indicate that MST network analyses are able to detect network changes in MS patients, which may correspond to changes in the core of functional brain networks. Moreover, these changes, such as a loss of hierarchical structure, are related to cognitive performance in MS. © 2013 Elsevier Inc.