Return to Revisions

Well, if $V=\{1,\ldots,n\}$, $(a_{ij})_{1\leqslant i,j\leqslant n}$ is the adjacency matrix, and it is non-singular, then its determinant (considered as a sum over permutations) has a non-zero term $\prod_i a_{i,\sigma(i)}$. It corresponds to a disjoint collection of cycles (these are cycles of the permutation $\sigma$ on $V$) which cover all vertices.