In
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
then the Tutte matrix is an ''n'' × ''n'' matrix A with entries
:
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