Tutte matrix

In graph theory, the Tutte matrix "A" of a graph "G" = ("V", "E") 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 formula_1 then the Tutte matrix is an "n" × "n" matrix A with entries
where the "x""ij" are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables "xij", "i < j" ): this coincides with the square of the pfaffian of the matrix "A" and is non-zero (as a polynomial) if and only if a perfect matching exists. (This polynomial is not the Tutte polynomial of "G".)
The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph.