We investigated whether functional brain networks are abnormally organized in Alzheimer's disease (AD). To this end, graph theoretical analysis was applied to matrices of functional connectivity of beta band-filtered electroencephalography (EEG) channels, in 15 Alzheimer patients and 13 control subjects. Correlations between all pairwise combinations of EEG channels were determined with the synchronization likelihood. The resulting synchronization matrices were converted to graphs by applying a threshold, and cluster coefficients and path lengths were computed as a function of threshold or as a function of degree K. For a wide range of thresholds, the characteristic path length L was significantly longer in the Alzheimer patients, whereas the cluster coefficient C showed no significant changes. This pattern was still present when L and C were computed as a function of K. A longer path length with a relatively preserved cluster coefficient suggests a loss of complexity and a less optimal organization. The present study provides further support for the presence of "small-world" features in functional brain networks and demonstrates that AD is characterized by a loss of small-world network characteristics. Graph theoretical analysis may be a useful approach to study the complexity of patterns of interrelations between EEG channels.