Petersen's Theorem
   HOME

TheInfoList



OR:

In the
mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
discipline of
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, Petersen's theorem, named after
Julius Petersen Julius Peter Christian Petersen (16 June 1839 in Sorø, West Zealand – 5 August 1910 in Copenhagen) was a Denmark, Danish mathematician. His contributions to the field of mathematics led to the birth of graph theory. Biography Petersen's in ...
, is one of the earliest results in graph theory and can be stated as follows:
Petersen's Theorem. Every
cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...
, bridgeless graph contains 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 with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
..
In other words, if a graph has exactly three edges at each vertex, and every edge belongs to a cycle, then it has a set of edges that touches every vertex exactly once.


Proof

We show that for every cubic, bridgeless graph we have that for every set the number of connected components in the graph
induced Induce may refer to: * Induced consumption * Induced innovation * Induced character * Induced coma * Induced menopause * Induced metric * Induced path * Induced topology * Induce (musician), American musician * Labor induction, stimulation of chil ...
by with an odd number of vertices is at most the cardinality of . Then by Tutte's theorem on perfect matchings contains a perfect matching. Let be a component with an odd number of vertices in the graph induced by the vertex set . Let denote the vertices of and let denote the number of edges of with one vertex in and one vertex in . By a simple double counting argument we have that :\sum\nolimits_ \deg_G(v) = 2, E_i, + m_i , where is the set of edges of with both vertices in . Since :\sum\nolimits_ \deg_G(v)= 3 , V_i, is an odd number and is an even number it follows that has to be an odd number. Moreover, since is bridgeless we have that . Let be the number of edges in with one vertex in and one vertex in the graph induced by . Every component with an odd number of vertices contributes at least 3 edges to , and these are unique, therefore, the number of such components is at most . In the worst case, is an independent set, and therefore . We get :, U, \geq\fracm\geq , \, , which shows that the condition of Tutte's theorem on perfect matchings holds.


History

The theorem is due to
Julius Petersen Julius Peter Christian Petersen (16 June 1839 in Sorø, West Zealand – 5 August 1910 in Copenhagen) was a Denmark, Danish mathematician. His contributions to the field of mathematics led to the birth of graph theory. Biography Petersen's in ...
, a Danish mathematician. It can be considered as one of the first results in
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
. The theorem appears first in the 1891 article "''Die Theorie der regulären graphs''". By today's standards Petersen's proof of the theorem is complicated. A series of simplifications of the proof culminated in the proofs by and . In modern textbooks Petersen's theorem is covered as an application of Tutte's theorem on perfect matchings.


Applications

* In a cubic graph with a perfect matching, the edges that are not in the perfect matching form a
2-factor In graph theory, a factor of a graph ''G'' is a spanning subgraph, i.e., a subgraph that has the same vertex set as ''G''. A ''k''-factor of a graph is a spanning ''k''-regular subgraph, and a ''k''-factorization partitions the edges of the gr ...
. By orienting the 2-factor, the edges of the perfect matching can be extended to paths of length three, say by taking the outward-oriented edges. This shows that every cubic, bridgeless graph decomposes into edge-disjoint paths of length three. * Petersen's theorem can also be applied to show that every
maximal planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
can be decomposed into a set of edge-disjoint paths of length three. In this case, the
dual graph In the mathematics, mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each p ...
is cubic and bridgeless, so by Petersen's theorem it has a matching, which corresponds in the original graph to a pairing of adjacent triangle faces. Each pair of triangles gives a path of length three that includes the edge connecting the triangles together with two of the four remaining triangle edges. * By applying Petersen's theorem to the dual graph of a
triangle mesh In computer graphics, a triangle mesh is a Types of mesh, type of polygon mesh. It comprises a set of triangles (typically in three dimensions) that are connected by their common Edge (geometry), edges or Vertex (geometry), vertices. Many gra ...
and connecting pairs of triangles that are not matched, one can decompose the mesh into cyclic strips of triangles. With some further transformations it can be turned into a single strip, and hence gives a method for transforming a triangle mesh such that its dual graph becomes
hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...
.


Extensions


Each edge belongs to some perfect matching in cubic bridgeless graphs

Schönberger strengthened Petersen's theorem in 1934 by showing that each edge of any cubic bridgeless graph belongs to some perfect matching.


Number of perfect matchings in cubic bridgeless graphs

It was conjectured by
Lovász Lovász (): * Chris Lovasz (born 1980), Canadian-British content creator * Gyöngyi Lovász (born 1959), Hungarian retired footballer * Irén Lovász (born 1961), Hungarian folk singer and ethnographer * Lázár Lovász (1942–2023), Hungarian at ...
and Plummer that the number of
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 with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
s contained in a
cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...
, bridgeless graph is exponential in the number of the vertices of the graph . The conjecture was first proven for bipartite, cubic, bridgeless graphs by , later for
planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...
, cubic, bridgeless graphs by . The general case was settled by , where it was shown that every cubic, bridgeless graph contains at least 2^ perfect matchings.


Algorithmic versions

discuss efficient versions of Petersen's theorem. Based on Frink's proof they obtain an algorithm for computing a perfect matching in a cubic, bridgeless graph with vertices. If the graph is furthermore
planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...
the same paper gives an algorithm. Their time bound can be improved based on subsequent improvements to the time for maintaining the set of bridges in a dynamic graph. Further improvements, reducing the time bound to or (with additional
random In common usage, randomness is the apparent or actual lack of definite pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. ...
ized
data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
s) , were given by .


Higher degree

If ''G'' is a regular graph of degree ''d'' whose
edge connectivity In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration ...
is at least ''d'' − 1, and ''G'' has an even number of vertices, then it has a perfect matching. More strongly, every edge of ''G'' belongs to at least one perfect matching. The condition on the number of vertices can be omitted from this result when the degree is odd, because in that case (by the
handshaking lemma In graph theory, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people ...
) the number of vertices is always even., Theorem 4, p. 285.


See also

* 2-factor theorem – related theorem by Petersen


Notes


References

* * * * * * * * * * *. * * * {{refend Matching (graph theory) Theorems in graph theory