Well, if the adjacency matrix is non-singular, its determinant has a non-zero term, which corresponds to a disjoint collection of cycles which cover all vertices.