Changes in functional connectivity across mental states can provide richer information about human cognition than simpler univariate approaches. Here, we applied a graph theoretical approach to analyze such changes in the lower alpha (8–10 Hz) band of EEG data from 26 subjects undergoing a mentally-demanding test of sustained attention: the Psychomotor Vigilance Test. Behavior and connectivity maps were compared between the first and last 5 min of the task. Reaction times were significantly slower in the final minutes of the task, showing a clear time-on-task effect. A significant increase was observed in weighted characteristic path length, a measure of the efficiency of information transfer within the cortical network. This increase was correlated with reaction time change. Functional connectivity patterns were also estimated on the cortical surface via source localization of cortical activities in 26 predefined regions of interest. Increased characteristic path length was revealed, providing further support for the presence of a reshaped global topology in cortical connectivity networks under fatigue state. Additional analysis showed an asymmetrical pattern of connectivity (right > left) in fronto-parietal regions associated with sustained attention, supporting the right-lateralization of this function. Interestingly, in the fatigue state, significance decreases were observed in left, but not right fronto-parietal connectivity. Our results indicate that functional network organization can change over relatively short time scales with mental fatigue, and that decreased connectivity has a meaningful relationship with individual difference in behavior and performance.