Abnormal functional connectivity (FC) has been commonly observed during alcohol use disorder (AUD). In this work, FC analysis has been performed by incorporating EEG-based graph-theoretic analysis and a machine learning (ML) framework. Brain FC was quantified with synchronization likelihood (SL). Undirected graphs for each channel pair were constructed involving the SL measures. Furthermore, the graph-based features such as minimum spanning tree, distances between nodes, and maximum flow between the graph nodes were computed, termed as EEG data matrix. The matrix was used as input data to the ML framework to classify the study participants. The ML framework was validated with data acquired from 30 AUD patients and an age-matched group of 30 healthy controls. In this study, the classifiers such as SVM (accuracy = 98.7), Naïve Bayes (accuracy = 88.6), and logistic regression (accuracy = 89) have shown promising discrimination results. The method was compared with two existing methods that also involve resting-state EEG data. The first method reported a classification accuracy of 91.7 while utilizing the time-based features such as Approximate Entropy (ApEn), Largest Lyapunov Exponent (LLE), Sample Entropy (SampEn), and four other Higher Order Spectra (HOS) features 1. The second method reported 95.8% accuracy involving wavelet-based signal energy 2. Since the study has utilized a small sample size, the generalization could not be possible. The FC-based graph-theoretic analysis in combination with ML methods could be used as an endophenotype for screening AUD patients. © Springer Nature Switzerland AG 2019.