Research on major depressive disorder (MDD) is one of the major fields of world health. Among all the solutions for depression identification, electroencephalography (EEG) is a very useful tool that has received a broad range of attention from researchers. In this study, we have proposed a novel deep learning method based on the spatial-temporal graph convolutional network (ST-GCN) in combination with depression-related functional connectivity graphs. In this work, the differential entropy (DE) feature of EEG is obtained and the adjacency matrix of the brain graph is created using the Phase Locking Value (PLV) matrix between EEG signal pairings. A proportional threshold is trained to select the critical edges of the brain graph to eliminate weak associations. For the classifier, a combined prior knowledge ST-GCN network constructed by spatial convolutional blocks and standard temporal convolutional blocks is employed to improve the spatial-temporal feature learning ability. Compared with other methods, our method obtains the best accuracy of 93.85%. The sound performance demonstrates the potential of the ST-GCN combined with the depression-related functional connectivity graph for clinical diagnostic and treatment prediction.