Brain connectivity analyses show considerable promise for understanding how our neural pathways gradually break down in aging and Alzheimer's disease (AD). Even so, we know very little about how the brain's networks change in AD, and which metrics are best to evaluate these changes. To better understand how AD affects brain connectivity, we analyzed anatomical connectivity based on 3-T diffusion-weighted images from 111 subjects (15 with AD, 68 with mild cognitive impairment, and 28 healthy elderly; mean age, 73.7±7.6 SD years). We performed whole brain tractography based on the orientation distribution functions, and compiled connectivity matrices showing the proportions of detected fibers interconnecting 68 cortical regions. We computed a variety of measures sensitive to anatomical network topology, including the structural backbone--the so-called "k-core"--of the anatomical network, and the nodal degree. We found widespread network disruptions, as connections were lost in AD. Among other connectivity measures showing disease effects, network nodal degree, normalized characteristic path length, and efficiency decreased with disease, while normalized small-worldness increased, in the whole brain and left and right hemispheres individually. The normalized clustering coefficient also increased in the whole brain; we discuss factors that may cause this effect. The proportions of fibers intersecting left and right cortical regions were asymmetrical in all diagnostic groups. This asymmetry may intensify as disease progressed. Connectivity metrics based on the k-core may help understand brain network breakdown as cognitive impairment increases, revealing how degenerative diseases affect the human connectome.