Determinant modulo $2$ of biadjacency matrix of bipartite graphs provide mod $2$ information on number of perfect matchings on bipartite graphs providing polynomial complexity in bipartite situations.


Is there a similar trick for general graphs which is in polynomial complexity?



Mod $2$ information on perfect matchings in general graphs
One can use [Pfaffians](https://en.wikipedia.org/wiki/Pfaffian) of the adjacency matrix. It will look like


$\text{pf}(A) = \sum\_{\sigma} \text{sgn}(\sigma) \cdot (\text{product of n entries of A})$


over certain permutations where the product is 1 if and only those $n$ edges make a perfect matching. Hence, we sum $\pm 1$ for each matching and obtain the count $\pmod 2$.


This idea can be used to try to exactly count perfect matching by weighting the entries of the adjacency matrix. This can be done by finding a [Pfaffian orientation](https://en.wikipedia.org/wiki/Pfaffian_orientation) (also called a Kasteleyn orientation). Such on orientation can be found efficiently for planar graphs using the [FKT algorithm](https://en.wikipedia.org/wiki/FKT_algorithm).


**Edit addition:** To answer original question more specifically. Yes, we can do this polynomial time. One way is arbitrarily oriented the graph so the adjacency matrix is skew-symmetric. Then $\text{pf}(A)^2 = \det(A)$. So, $\text{pf}(A)$ and $\det(A)$ have the same parity and we can compute will Gaussian elimination efficiently.


