Tutte matrix

From Citizendium
Jump to navigation Jump to search
This article is a stub and thus not approved.
Main Article
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
This editable Main Article is under development and subject to a disclaimer.

In graph theory, the Tutte matrix 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 V has 2n elements then the Tutte matrix is a 2n × 2n matrix A with entries

where the xij 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. (It should be noted that this is not the Tutte polynomial of G.)

The Tutte matrix is a generalisation of the Edmonds matrix for a balanced bipartite graph.