Graph theoretical measures have frequently been used to study disrupted connectivity in Alzheimer’s disease human brain connectomes. However, prior studies have noted that differences in graph creation methods are confounding factors that may alter the topological observations found in these measures. In this study, we conduct a novel investigation regarding the effect of parcellation scale on graph theoretical measures computed for fiber density networks derived from diffusion tensor imaging. We computed 4 network-wide graph theoretical measures of average clustering coefficient, transitivity, characteristic path length, and global efficiency, and we tested whether these measures are able to consistently identify group differences among healthy control (HC), mild cognitive impairment (MCI), and AD groups in the Alzheimer’s Disease Neuroimaging Initiative (ADNI) cohort across 5 scales of the Lausanne parcellation. We found that the segregative measure of transtivity offered the greatest consistency across scales in distinguishing between healthy and diseased groups, while the other measures were impacted by the selection of scale to varying degrees. Global efficiency was the second most consistent measure that we tested, where the measure could distinguish between HC and MCI in all 5 scales and between HC and AD in 3 out of 5 scales. Characteristic path length was highly sensitive to the variation in scale, corroborating previous findings, and could not identify group differences in many of the scales. Average clustering coefficient was also greatly impacted by scale, as it consistently failed to identify group differences in the higher resolution parcellations. From these results, we conclude that many graph theoretical measures are sensitive to the selection of parcellation scale, and further development in methodology is needed to offer a more robust characterization of AD’s relationship with disrupted connectivity.