To better characterize the cognitive processes and mechanisms that are associated with deception, wavelet coherence was employed to evaluate functional connectivity between different brain regions. Two groups of subjects were evaluated for this purpose: 32 participants were required to either tell the truth or to lie when facing certain stimuli, and their electroencephalogram signals on 12 electrodes were recorded. The experimental results revealed that deceptive responses elicited greater connectivity strength than truthful responses, particularly in the θ band on specific electrode pairs primarily involving connections between the prefrontal/frontal and central regions and between the prefrontal/frontal and left parietal regions. These results indicate that these brain regions play an important role in executing lying responses. Additionally, three time- and frequency-dependent functional connectivity networks were proposed to thoroughly reflect the functional coupling of brain regions that occurs during lying. Furthermore, the wavelet coherence values for the connections shown in the networks were extracted as features for support vector machine training. High classification accuracy suggested that the proposed network effectively characterized differences in functional connectivity between the two groups of subjects over a specific time-frequency area and hence could be a sensitive measurement for identifying deception.