This paper elucidates the relation between network dynamics and graph theory. A new general method to determine global stability of total synchronization in networks with different topologies is proposed. This method combines the Lyapunov function approach with graph theoretical reasoning. In this context, the main step is to establish a bound on the total length of all paths passing through an edge on the network connection graph. In particular, the method is applied to the study of synchronization in rings of $2K$-nearest neighbor coupled oscillators. A rigorous bound is given for the minimum coupling strength sufficient for global synchronization of all oscillators. This bound is explicitly linked with the average path length of the coupling graph. Contrary to the Master Stability function approach developed by Pecora and Carroll, the Connection Graph Stability method leads to global stability of synchronization, and it permits not only constant, but also time-dependent interaction coefficients. In a companion paper ("Blinking model and synchronization in small-world networks with a time-varying coupling," see this issue), this method is extended to the blinking model of small-world networks where, in addition to the fixed $2K$-nearest neighbor interactions, all the remaining links are rapidly switched on and off independently of each other.