Determinants in Graph Theory In graph theory, we work with adjacency matrices which define the connections between the vertices. These matrices have various linear-algebraic properties. For example, their trace can be calculated (it is zero in the case of a loopless graph, i.e., an irreflexive symmetric binary relation). And we can also calculate their determinants. 
How would you interpret the determinant in the context of a graph?
For example, I teach network theory and the calculation of 'eigenvector centrality' requires the use of determinants. But the general question always comes up: what does the determinant mean in the context of the network (or graph)? Does it tell me of a property of the network that is useful?
In essence, I am trying to find a user-friendly interpretation of determinants in the context of networks or graphs.
I would be grateful for any assistance.
 A: Let $G$ be a graph with adjacency matrix $A$. Let $s(G)$ be the number of connected components of $G$ that are cycles and $r(G)$ the number of connected components that are either $K_2$ or even cycles. Then $$\det(A) = \sum_{H} (-1)^{r(H)} 2^{s(H)}$$ where the sum is over all spanning subgraphs $H$ of $G$ that have only $K_2$ and cycles as their connected components.
In particular if $T$ is a tree the determinant of its adjacency matrix is $\pm$ the number of perfect matchings of $T$.
A relevant passage from N. Biggs: Algebraic Graph Theory. Second Edition. Cambridge University Press, is:

This identity can be generalized to all other coefficients of the characteristic polynomial of $A.$ For more information check the chapter "Determinant expansions" of Biggs' book on algebraic graph theory. 
A: If your graph is directed and each edge has weight $1$ then the determinant counts the number of not-necessarily-connected-cycles (that is subgraphs being disjoint unions of connected cycles) passing through every vertex of the graph. The cycle is counted as $-1$ if the number of its components has different parity than the number of vertices of the graph, otherwise it is counted as $1$.
