Tutte matrix

Ingraph theory,theTutte matrixAof agraphG= (V,E) is amatrixused to determine the existence of aperfect matching:that is, a set ofedgeswhich is incident with eachvertexexactly once.

If the set of vertices is$V=\{1,2,\dots,n\}$then the Tutte matrix is ann×nmatrix A with entries

$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 thex_ijare indeterminates. Thedeterminantof thisskew-symmetricmatrix is then a polynomial (in the variablesx_ij,i < j): this coincides with the square of thepfaffianof the matrixAand is non-zero (as a polynomial) if and only if a perfect matching exists. (This polynomial is not theTutte polynomialofG.)

The Tutte matrix is named afterW. T. Tutte,and is a generalisation of theEdmonds matrixfor a balancedbipartite graph.

References

• R. Motwani, P. Raghavan (1995).Randomized Algorithms.Cambridge University Press. p. 167.
• Allen B. Tucker (2004).Computer Science Handbook.CRC Press. p. 12.19.ISBN1-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.Retrieved2008-06-15.