Control of vehicle formations has emerged as a topic of significant interest to the controls community. In this paper, we merge tools from graph theory and control theory to derive stability criteria for vehicle formations. The interconnection between vehicles (i.e., which vehicles are sensed by other vehicles) is modeled as a graph, and the eigenvalues of the Laplacian matrix of the graph are used in stating a Nyquist-like stability criterion. The relationship between the location of the Laplacian eigenvalues and the graph structure is used to identify desirable and undesirable formation interconnection topologies.