Despite the apparent importance of mental fatigue detection, a reliable application is hindered due to the incomprehensive understanding of the neural mechanisms of mental fatigue. In this paper, we investigated the topological alterations of functional brain networks in the theta band (4 – 7 Hz) of electroencephalography (EEG) data from 40 male subjects undergoing two distinct fatigue-inducing tasks: a low-intensity one-hour simulated driving and a high-demanding half-hour sustained attention task [psychomotor vigilance task (PVT)]. Behaviorally, subjects demonstrated a robust mental fatigue effect, as reflected by significantly declined performances in cognitive tasks prior and post these two tasks. Furthermore, characteristic path length presented a positive correlation with task duration, which led to a significant increase between the first and the last five minutes of both tasks, indicating a fatigue-related disruption in information processing efficiency. However, significantly increased clustering coefficient was revealed only in the driving task, suggesting distinct network reorganizations between the two fatigue-inducing tasks. Moreover, high accuracy (92% for driving; 97% for PVT) was achieved for fatigue classification with apparently different discriminative functional connectivity features. These findings augment our understanding of the complex nature of fatigue-related neural mechanisms and demonstrate the feasibility of using functional connectivity as neural biomarkers for applicable fatigue monitoring.