Tutte matrix

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2024) (Learn how and when to remove this message)

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

${\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 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.

• 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). "The factorization of linear graphs" (PDF). J. London Math. Soc. 22 (2): 107–111. doi:10.1112/jlms/s1-22.2.107. Retrieved 2008-06-15.

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e

This article about matrices is a stub. You can help Wikipedia by expanding it.

• v
• t
• e