Accumulating efforts have been made to discover effective solutions for fatigue recovery with the ultimate aim of reducing adverse consequences of mental fatigue in real life. The previously-reported behavioral benefits of physical exercise on mental fatigue recovery prompted us to investigate the restorative effect and reveal the underlying neural mechanisms. Specifically, we introduced an empirical method to investigate the beneficial effect of physical exercise on the reorganization of EEG functional connectivity (FC) in a two-session experiment where one session including a successive 30-min psychomotor vigilance task (PVT) (No-intervention session) compared to an insertion of a mid-task 15-min cycling exercise (Intervention session). EEG FC was obtained from 21 participants and quantitatively assessed via graph theoretical analysis and a classification framework. The findings demonstrated the effectiveness of exercise intervention on behavioral performance as shown in improved reaction time and response accuracy. Although we found significantly altered network alterations towards the end of experiment in both sessions, no significant differences between the two sessions and no interaction between session and time were found in EEG network topology. Further interrogation of functional connectivity through classification analysis showed decreased FC in distributed brain areas, which may lead to the significant reduction of network efficiency in both sessions. Moreover, we showed distinct patterns of FC alterations between the two sessions, indicating different information processing strategies adopted in the intervention session. In sum, these results provide some of the first quantitative insights into the complex neural mechanism of exercise intervention for fatigue recovery and lead a new direction for further application research in real-world situations.