Classification of mental tasks from electroencephalogram (EEG) signals play a crucial role in designing various brain-computer interface (BCI) applications. Most of the current techniques consider each channel as independent, neglecting the functional connectivity of the brain during mental activity and are primarily subject specific. This paper proposes a graph signal representation to classify a pair of mental tasks using multi-channel EEG signals (MTMC-EEG) with cross subject classification within the database. Here, each channel of EEG signal corresponds to nodes of the task based graph whose EEG time series resides on the respective nodes. Functional connectivity of the brain between these nodes is obtained using smoothness constraint based Graph Signal Processing (GSP) technique. Graph spectral features namely, two-norm total variation of eigen vector (TNTV) corresponding to weighted adjacency matrix, graph Laplacian energy (GLE) using eigenvalues of Laplacian matrix and convex sum of TNTV and GLE in the form of joint total variation energy (JTVE) are proposed in this paper. The performance of the proposed methodology is evaluated on publicly available two different databases of MTMC EEG signals using benchmark classifiers and compared with the state of the art. Further, the superiority of the proposed metric obtained from the smoothened graph of GSP technique is validated by comparing it with Pearson correlation and Gaussian radial basis function (RBF) based functional connectivity in terms of accuracy, F-Score, and information transfer rate (ITR). The robustness of the proposed method is validated by adding white Gaussian noise (AWGN) to the EEG signals using different SNRs. © 2001-2012 IEEE.