Tutte matrix
In graph theory, the Tutte matrix A of a graph G = is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once.
If the set of vertices is then the Tutte matrix is an n-by-n skew-symmetric matrix A with entries
where the xij are indeterminates. The determinant of this matrix is then a polynomial : this coincides with the square of the Pfaffian of the matrix A and is non-zero if and only if a perfect matching exists.
The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph.