We present a novel algorithm for the simultaneous segmentation and anatomical labeling of the cerebral vasculature. The method first constructs an over-complete graph capturing the vasculature. It then selects and labels the subset of edges that most likely represents the true vasculature. Unlike existing approaches that first attempt to obtain a good segmentation and then perform labeling, we jointly optimize for both by simultaneously taking into account the image evidence and the prior knowledge about the geometry and connectivity of the vasculature. This results in an Integer Program (IP), which we solve optimally using a branch-and-cut algorithm. We evaluate our approach on a public dataset of 50 cerebral MRA images, and demonstrate that it compares favorably against state-of-the-art methods.