This paper examines stability properties of distance-based formations. These are formations encoded by inter-agent relative distances. A negative gradient control law is proposed and is shown to be provably correct when the formation graph is a tree. Moreover, it is shown that the tree structure is a necessary and sufficient condition for distancebased formation stabilization with negative gradient control laws. For graphs that contain cycles, a characterization of the resulting equilibria is given based on the properties of the cycle space of the graph. The results are also applied to flocking motion for double integrator agents.