Dementias such as Alzheimer disease (AD) and mild cognitive impairment (MCI) lead to problems with memory, language, and daily activities resulting from damage to neurons in the brain. Given the irreversibility of this neuronal damage, it is crucial to find a biomarker to distinguish individuals with these diseases from healthy people. In this study, we construct a brain function network based on electroencephalography data to study changes in AD and MCI patients. Using a graph-theoretical approach, we examine connectivity features and explore their contributions to dementia recognition at edge, node, and network levels. We find that connectivity is reduced in AD and MCI patients compared with healthy controls. We also find that the edge-level features give the best performance when machine learning models are used to recognize dementia. The results of feature selection identify the top 50 ranked edge-level features constituting an optimal subset, which is mainly connected with the frontal nodes. A threshold analysis reveals that the performance of edge-level features is more sensitive to the threshold for the connection strength than that of node- and network-level features. In addition, edge-level features with a threshold of 0 provide the most effective dementia recognition. The K-nearest neighbors (KNN) machine learning model achieves the highest accuracy of 0.978 with the optimal subset when the threshold is 0. Visualization of edge-level features suggests that there are more long connections linking the frontal region with the occipital and parietal regions in AD and MCI patients compared with healthy controls. Our codes are publicly available at https://github.com/Debbie-85/eeg-connectivity.