Tutte matrix

{{No footnotes|date=November 2024}}

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 $V\; =\; \backslash \{1,\; 2,\; \backslash dots\; ,\; n\backslash \}$ then the Tutte matrix is an n-by-n matrix A with entries

:

-x_{ji}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i>j\\

0\;\;\;\;\mbox{otherwise} \end{cases}

where the x_ij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables x_ij, 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.