The determinant of the adjacency matrix of a graph.
For a labelled graph $G$ with vertices $\{1,\ldots,n\}$, the adjacency matrix is the matrix $(a_{ij})$ with $a_{ij} = 1$ if the vertices $i$ and $j$ are joined by an edge in $G$.
Since the determinant is invariant under simultaneous row and column permutations, the determinant of the adjacency is well-defined for an unlabelled graph.
According to [2], Equation 8, this determinant can be computed as follows: let $s(G)$ be the number of connected components of $G$ that are cycles and $r(G)$ the number of connected components that equal $K_2$. Then $$\det(A) = \sum_{H} (-1)^{r(H)} 2^{s(H)}$$ where the sum is over all spanning subgraphs $H$ of $G$ that have as connected components only $K_2$'s and cycles.

[1] wikipedia:Adjacency_matrix
[2] Harary, F. The determinant of the adjacency matrix of a graph MathSciNet:0144330

Dec 26, 2015 at 17:54 by Christian Stump

Dec 29, 2015 at 20:22 by Martin Rubey