Brain connectivity-based methods are efficient and reliable for assessing the mental workload during high task demands as the human brain is functionally interconnected during any psychological task. On the other hand, the graph theory approach is a mathematical study that draws the pairwise relationships between objects. This paper covers the deployment of graph theory concepts on the brain connectivity methods to find the complex underlying behaviors of the brain in the simplest way. Furthermore, in this work, mental workload assessments on multimedia animations were performed using a brain connectivity approach based on partial directed coherence (PDC) with graph theory analysis. Electroencephalography (EEG) data were collected from 34 adult participants at baseline and during multimedia learning tasks. The results revealed that the EEG-based connectivity approach with graph theory offers more promising results than the traditional feature extraction techniques. The connectivity approach achieved an accuracy of 85.77 in comparison with the 78.50 accuracy achieved by the existing feature extraction techniques. It is concluded that the proposed PDC method with graph theory network analysis is a better solution for cognitive load assessment during any cognitive task. © 2020, Springer-Verlag London Ltd., part of Springer Nature.