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

A i j = { x i j if ( i , j ) ∈ E and i < j − x j i if ( i , j ) ∈ E and i > j 0 otherwise {\displaystyle A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i<j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i>j\\0\;\;\;\;{\mbox{otherwise}}\end{cases}}}

where the xij are indeterminates. The determinant of this 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.

  • R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167.
  • Allen B. Tucker (2004). Computer Science Handbook. CRC Press. p. 12.19. ISBN 1-58488-360-X.
  • W.T. Tutte (April 1947). (PDF). J. London Math. Soc. 22 (2): 107–111. doi:.