This paper studies the coupling between dynamics that span multiple time-scales in distributed networked systems. In particular, we consider the evolution of the consensus dynamics interacting with fast nonlinear vehicle dynamics as well as its progress over a state-dependent graphs with slow-varying weight dynamics. Graph-based guarantees are provided that certify the existence of a separation principle across time-scales. Further, we quantify the role of the network’s structure in ensuring stability of the composite multi-time-scale system. Graph spectral measures are calculated providing designers a network structure approach to improve performance and/or stability of the coupled system. Examples are presented illustrating the results.