The organizational network changes in the human brain across lifespan have been mapped using functional and structural connectivity data. Brain network changes provide valuable insights into the processes underlying senescence. Nonetheless, the altered network density in elderly severely compromises the usefulness of network analysis in to study the aging brain. We successfully circumvented this problem by focussing on the critical structural network backbone, using a robust tree representation. Whole-brain networks’ minimum spanning trees were determined in a dataset of diffusion-weighted images from 382 healthy subjects, ranging in age from 20.2 to 86.2 years. Tree-based metrics were compared with classical network metrics. In contrast to the tree-based metrics, classical metrics were highly influenced by age-related changes in network density. Tree-based metrics showed linear and non-linear correlation across adulthood and are in close accordance with results from previous histopathological characterizations of the changes in white matter integrity in the aging brain.