This paper clarifies the relation between synchronization and graph topology. Applying the Connection Graph Stability method developed by Belykh et al. [2004a] to the study of synchronization in networks of coupled oscillators, we show which graph properties matter for synchronization. In particular, while we explicitly link the stability of synchronization with the average path length for a wide class of coupling graphs, we prove by a simple argument that the average path length is not always the crucial quantity for synchronization. We also show that synchronization in scale-free networks can be described by means of regular networks with a star-like coupling structure. Finally, by considering an example of coupled Hindmarsh–Rose neuron models, we demonstrate how global stability of synchronization depends on the parameters of the individual oscillator.