Petersen's theorem

File:Petersen-graph-factors.svg (red edges), in the Petersen graph. Since the Petersen graph is cubic and bridgeless, it meets the conditions of Petersen's theorem.]]

File:Sylvester counter.svg

In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.{{harvtxt|Petersen|1891}}.

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 {{math|G {{=}} (V, E)}} we have that for every set {{math|U ⊆ V}} the number of connected components in the graph induced by {{math|V − U}} with an odd number of vertices is at most the cardinality of {{math|U}}. Then by the Tutte theorem {{math|G}} contains a perfect matching.

Let {{math|G_i}} be a component with an odd number of vertices in the graph induced by the vertex set {{math|V − U}}. Let {{math|V_i}} denote the vertices of {{math|G_i}} and let {{math|m_i}} denote the number of edges of {{math|G}} with one vertex in {{math|V_i}} and one vertex in {{math|U}}. By a simple double counting argument we have that

: $\sum\nolimits_{v\in V_i} \deg_G(v) = 2|E_i| + m_i ,$

where {{math|E_i}} is the set of edges of {{math|G_i}} with both vertices in {{math|V_i}}. Since

: $\sum\nolimits_{v \in V_i} \deg_G(v)= 3 |V_i|$

is an odd number and {{math|2|E_i|}} is an even number it follows that {{math|m_i}} has to be an odd number. Moreover, since {{math|G}} is bridgeless we have that {{math|m_i ≥ 3}}.

Let {{math|m}} be the number of edges in {{math|G}} with one vertex in {{math|U}} and one vertex in the graph induced by {{math|V − U}}. Every component with an odd number of vertices contributes at least 3 edges to {{math|m}}, and these are unique, therefore, the number of such components is at most {{math|m/3}}. In the worst case, {{math|U}} is an independent set, and therefore {{math|m ≤ 3|U|}}. We get

: $|U|\geq\frac{1}{3}m\geq |\{\text{components with an odd number of vertices}\}| ,$

which shows that the condition of Tutte theorem holds.

History

The theorem is due to Julius Petersen, a Danish mathematician. It can be considered as one of the first results in graph theory. 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 {{harvtxt|Frink|1926}} and {{harvtxt|König|1936}}.

In modern textbooks Petersen's theorem is covered as an application of Tutte's theorem.

Applications

In a cubic graph with a perfect matching, the edges that are not in the perfect matching form a 2-factor. 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.See for example {{harvtxt|Bouchet|Fouquet|1983}}.
Petersen's theorem can also be applied to show that every maximal planar graph can be decomposed into a set of edge-disjoint paths of length three. In this case, the dual graph 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.{{harvtxt|Häggkvist|Johansson|2004}}.
By applying Petersen's theorem to the dual graph of a triangle mesh 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.{{sfnp|Meenakshisundaram|Eppstein|2004}}

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 and Plummer that the number of perfect matchings contained in a cubic, bridgeless graph is exponential in the number of the vertices of the graph {{math|n}}.{{sfnp|Lovász|Plummer|1986}}

The conjecture was first proven for bipartite, cubic, bridgeless graphs by {{harvtxt|Voorhoeve|1979}}, later for planar, cubic, bridgeless graphs by {{harvtxt|Chudnovsky|Seymour|2012}}. The general case was settled by {{harvtxt|Esperet|Kardoš|King|Králʼ|2011}}, where it was shown that every cubic, bridgeless graph contains at least $2^{n/3656}$ perfect matchings.

= Algorithmic versions =

{{harvtxt|Biedl|Bose|Demaine|Lubiw|2001}} discuss efficient versions of Petersen's theorem. Based on Frink's proof{{harvtxt|Frink|1926}}. they obtain an {{math|O(n log⁴ n)}} algorithm for computing a perfect matching in a cubic, bridgeless graph with {{math|n}} vertices. If the graph is furthermore planar the same paper gives an {{math|O(n)}} algorithm. Their {{math|O(n log⁴ n)}} time bound can be improved based on subsequent improvements to the time for maintaining the set of bridges in a dynamic graph.{{sfnp|Thorup|2000}} Further improvements, reducing the time bound to {{math|O(n log² n)}} or (with additional randomized data structures) {{math|O(n log n (log log n)³)}}, were given by {{harvtxt|Diks|Stanczyk|2010}}.

=Higher degree=

If G is a regular graph of degree d whose edge connectivity 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) the number of vertices is always even.{{harvtxt|Naddef|Pulleyblank|1981}}, Theorem 4, p. 285.

Notes

References

{{citation

| last1 = Biedl | first1 = Therese C. | author1-link = Therese Biedl

| last2 = Bose | first2 = Prosenjit | author2-link = Jit Bose

| last3 = Demaine | first3 = Erik D. | author3-link = Erik Demaine

| last4 = Lubiw | first4 = Anna | author4-link = Anna Lubiw

| doi = 10.1006/jagm.2000.1132

| issue = 1

| journal = Journal of Algorithms

| mr = 1810434

| pages = 110–134

| title = Efficient algorithms for Petersen's matching theorem

| volume = 38

| year = 2001}}

{{citation

| last1 = Bouchet | first1 = André

| last2 = Fouquet | first2 = Jean-Luc

| contribution = Trois types de décompositions d'un graphe en chaînes

| doi = 10.1016/S0304-0208(08)73380-2

| language = French

| mr = 0841287

| pages = 131–141

| publisher = North-Holland

| series = North-Holland Mathematics Studies

| title = Combinatorial Mathematics: Proceedings of the International Colloquium on Graph Theory and Combinatorics (Marseille-Luminy, 1981)

| volume = 75

| year = 1983| isbn = 978-0-444-86512-0

}}

{{citation

| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky

| last2 = Seymour | first2 = Paul

| authorlink2= Paul Seymour (mathematician)

| doi = 10.1007/s00493-012-2660-9

| issue = 4

| journal = Combinatorica

| mr = 2965284

| pages = 403–424

| title = Perfect matchings in planar cubic graphs

| volume = 32

| year = 2012}}

{{citation

| last1 = Diks | first1 = Krzysztof

| last2 = Stanczyk | first2 = Piotr

| editor1-last = van Leeuwen | editor1-first = Jan | editor1-link = Jan van Leeuwen

| editor2-last = Muscholl | editor2-first = Anca | editor2-link = Anca Muscholl

| editor3-last = Peleg | editor3-first = David | editor3-link = David Peleg (computer scientist)

| editor4-last = Pokorný | editor4-first = Jaroslav

| editor5-last = Rumpe | editor5-first = Bernhard | editor5-link = Bernhard Rumpe

| contribution = Perfect matching for biconnected cubic graphs in {{math|O(n log² n)}} time

| doi = 10.1007/978-3-642-11266-9_27

| pages = 321–333

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = SOFSEM 2010: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23–29, 2010, Proceedings

| volume = 5901

| year = 2010| isbn = 978-3-642-11265-2

}}

{{citation

| last1 = Esperet | first1 = Louis

| last2 = Kardoš | first2 = František

| last3 = King | first3 = Andrew D.

| last4 = Králʼ | first4 = Daniel | author4-link = Daniel Kráľ

| last5 = Norine | first5 = Serguei

| doi = 10.1016/j.aim.2011.03.015 | doi-access=free

| issue = 4

| journal = Advances in Mathematics

| mr = 2799808

| pages = 1646–1664

| title = Exponentially many perfect matchings in cubic graphs

| volume = 227

| year = 2011| arxiv = 1012.2878

}}

{{citation

| doi = 10.2307/1967699

| volume = 27

| issue = 4

| pages = 491–493

| authorlink = Orrin Frink

| last = Frink

| first = Orrin

| title = A proof of Petersen's theorem

| journal = Annals of Mathematics

| series = Second Series

| year = 1926

| jstor = 1967699

}}

{{citation

| last1 = Häggkvist | first1 = Roland

| last2 = Johansson | first2 = Robert

| doi = 10.1016/j.disc.2003.11.017

| issue = 1–3

| journal = Discrete Mathematics

| mr = 2061501

| pages = 263–266

| title = A note on edge-decompositions of planar graphs

| volume = 283

| year = 2004| doi-access = free

}}

{{Citation

| last = König

| first = Dénes

|authorlink=Dénes Kőnig

| title = Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe.

| year = 1936

}}

{{Cite Lovasz Plummer}}
{{citation

| last1 = Meenakshisundaram | first1 = Gopi

| last2 = Eppstein | first2 = David | author2-link = David Eppstein

| arxiv = cs.CG/0405036

| contribution = Single-strip triangulation of manifolds with arbitrary topology

| pages = 371–379

| series = Computer Graphics Forum

| title = Proc. 25th Conf. Eur. Assoc. for Computer Graphics (Eurographics '04)

| doi = 10.1111/j.1467-8659.2004.00768.x

| volume = 23

| year = 2004| issue = 3

}}

{{citation

| last1 = Naddef | first1 = D.

| last2 = Pulleyblank | first2 = W. R. | author2-link = William R. Pulleyblank

| doi = 10.1016/0012-365X(81)90006-6

| issue = 3

| journal =Discrete Mathematics

| mr = 613406

| pages = 283–291

| title = Matchings in regular graphs

| volume = 34

| year = 1981| doi-access = free

}}.

{{Citation

| volume = 15

| pages = 193–220

| last = Petersen

| first = Julius

| authorlink = Julius Petersen

| title = Die Theorie der regulären graphs

| journal = Acta Mathematica

| year = 1891

| doi = 10.1007/BF02392606

| doi-access = free

}}

{{citation|first=Mikkel|last=Thorup|authorlink=Mikkel Thorup|year=2000|pages=343–350|doi=10.1145/335305.335345|contribution=Near-optimal {{Sic|hide=y|fully|-}}dynamic graph connectivity|title=Proc. 32nd ACM Symposium on Theory of Computing|isbn=1-58113-184-4|mr=2114549}}
{{citation

| authorlink = Marc Voorhoeve

| last = Voorhoeve | first = Marc

| doi = 10.1016/1385-7258(79)90012-X

| issue = 1

| journal = Indagationes Mathematicae

| mr = 0528221

| pages = 83–86

| title = A lower bound for the permanents of certain (0,1)-matrices

| volume = 82

| year = 1979| doi-access = free

}}

Category:Matching (graph theory)

Category:Theorems in graph theory

Petersen's theorem

Proof

History

Applications

Extensions

= Each edge belongs to some perfect matching in cubic bridgeless graphs =

= Number of perfect matchings in cubic bridgeless graphs=

= Algorithmic versions =

=Higher degree=

See also

Notes

References