Discriminating mental states from brain signals is crucial for many applications in cognitive and clinical neuroscience. Most of the studies relied on the feature extraction from the activity of single brain areas, thus neglecting the potential contribution of their functional coupling, or connectivity. Here, we consider spectral coherence and imaginary coherence to infer brain connectivity networks from electroencephalographic (EEG) signals recorded during motor imagery and resting states in a group of healthy subjects. By using a graph theoretic approach, we then extract the weighted node degree from each network and evaluate its ability to discriminate the two mental states as a function of the number of available observations. The obtained results show that the features extracted from spectral coherence networks outperform those obtained from imaginary coherence in terms of significant difference, neurophysiological interpretation and reliability with fewer observations. Taken together, these findings suggest that graph algebraic descriptors of brain connectivity networks can be further explored to classify mental states.