graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Tutte matrix ''A'' of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

''G'' = (''V'', ''E'') is a matrix used to determine the existence of a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactl ...

: that is, a set of

edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed ...

s which is incident with each

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet * Vertex (computer graphics), a data structure that describes the positio ...

exactly once. If the set of vertices is

V = \

then the Tutte matrix is an ''n'' × ''n'' matrix A with entries :

A_ = \begin x_\;\;\mbox\;(i,j) \in E \mbox i j\\
0\;\;\;\;\mbox \end

where the ''x''_''ij'' are indeterminates. The

determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...

of this skew-symmetric matrix is then a polynomial (in the variables ''x_ij'', ''i < j'' ): this coincides with the square of the

pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...

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 The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...

of ''G''.) The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph.

References

* * * Algebraic graph theory Matching (graph theory) Matrices {{combin-stub