Petersen's theorem

The Petersen's theorem is a mathematical theorem from graph theory . It says that every cubic graph without a bridge contains a perfect match . Petersen's theorem is considered to be one of the earliest results of graph theory. It is named after the Danish mathematician Julius Petersen .

sentence

Petersen's theorem says:

Every cubic graph without a bridge contains a perfect match.

This means that if every node in a graph has exactly three neighboring edges and every edge can be expanded to a circle , then there is a selection of edges that each node touches exactly once.

proof

One shows that for every cubic graph without bridges the following applies: For every node set , the number of connected components in the graph induced by with an odd number of nodes is at most as large as the number of nodes in itself. Then by Tutte's theorem that possesses a perfect pairing. ${\displaystyle G=(V,E)}$ ${\displaystyle U\subseteq V}$ ${\displaystyle V-U}$ ${\displaystyle U}$ ${\displaystyle G}$

Let be a connected component with an odd number of nodes in the induced graph. Let the nodes in and the number of edges in the section of be denoted by. Summing up the nodes in yields ${\displaystyle G_{i}}$ ${\displaystyle V-U}$ ${\displaystyle V_{i}}$ ${\displaystyle G_{i}}$ ${\displaystyle m_{i}}$ ${\displaystyle V_{i}}$ ${\displaystyle V_{i}}$

${\displaystyle \sum _{v\in V_{i}}\deg(v)+m_{i}=2|E_{i}|}$,

where the edges in are designated by at least one node in . There ${\displaystyle E_{i}}$ ${\displaystyle G}$ ${\displaystyle V_{i}}$

${\displaystyle \sum _{v\in V_{i}}\deg(v)=3|V_{i}|}$

is an odd number, and an even number, it follows that it must be an odd number. Since no bridge owns, must apply. ${\displaystyle 2|E_{i}|}$ ${\displaystyle m_{i}}$ ${\displaystyle G}$ ${\displaystyle m_{i}\geq 3}$

Now let be the number of all cutting edges of in . According to the argument in the previous paragraph, the number of connected components with an odd number of nodes is at most 3 . In the worst case, each edge with a node contributes to a connected component with an odd number of nodes . It follows that , and the requirements of Tutte's theorem are thus fulfilled. ${\displaystyle m}$ ${\displaystyle U}$ ${\displaystyle G}$ ${\displaystyle m}$ ${\displaystyle U}$ ${\displaystyle 3m\leq |U|}$

history

The theorem was first formulated and proven by Julius Petersen. It is considered one of the first results in the field of graph theory and was published in 1891 in the essay The Theory of Regular Graphs . As things stand today, Petersen's original evidence is considered complicated. A series of simplifications led to the evidence of Orrin Frink (1926) and Dénes König (1936).

In current textbooks, Petersen's theorem is treated as an application of Tutte's theorem .

Applications

• In a cubic graph with a perfect match, the edges outside the match form a 2-factor . With a certain orientation of the 2-factor, the edges of the pairing can be extended by two edges each to a path of length three. This shows that every cubic graph without bridges can be covered with edge-disjoint paths of length three.
• With the help of Petersen's theorem one can also show that every maximal planar graph can be covered with edge-disjoint paths of length three. Since the dual graph of such a graph is cubic and contains no bridges, one can find a perfect match there, which in the original graph belongs to two triangles that share an edge. These common edges can be extended to ways of length three in such a way that no edge appears in several of these extensions.
• A triangular lattice can be modified with the help of Petersen's theorem so that a Hamilton path exists in the dual graph of the lattice.

Extensions

Number of perfect pairings in cubic graphs without a bridge

Of László Lovász and Michael Plummer has been suggested that each cubic graph with nodes and without a bridge an exponential number (in possesses) of perfect matches. This conjecture was proven in 1979 for bipartite graphs by Marc Voorhoeve, and in 2012 for planar graphs by Maria Chudnovsky and Paul Seymour . The general case was finally discovered in 2011 by Lois Esperet et al. a. proven. Here it was shown that every cubic graph without bridges and with nodes has at least perfect pairings. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{n/3656}}$

Algorithmic versions

From Therese Biedl u. a. efficient algorithmic variants of Petersen's theorem were examined. Based on Frink's proof, they developed an algorithm to compute a perfect match in cubic graphs without bridges with nodes. If it is also a planar graph, the same article gives an algorithm. The runtime can be further improved through subsequent improvements to the data structures used in the algorithm . Further improvements resulted in an algorithm. When using randomized data structures, the runtime can even be improved. ${\displaystyle O(n\log ^{4}n)}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle O(n\log n\,(\log \log n)^{3})}$

Individual evidence

1. ↑ ^{a b} Julius Petersen : The theory of regular graphs . In: Acta Mathematica . 15, 1891, pp. 193-220. doi : 10.1007 / BF02392606 .
2. ^ Orrin Frink: A proof of Petersen's theorem . In: Annals of Mathematics . tape 27 , no. 4 , 1926, pp. 491-493 , doi : 10.2307 / 1967699 .
3. ↑ Dénes König : Theory of finite and infinite graphs; combinatorial topology of the route complexes . Academic Publishing Company, Leipzig 1936.
4. ^ André Bouchet, Jean-Luc Fouquet: Trois types de décompositions d'un graphe en chaînes . In: P. Camion, D. Bresson, C. Berge, F. Sterboul (Eds.): Combinatorial Mathematics: Proceedings of the International Colloquium on Graph Theory and Combinatorics (Marseille-Luminy, 1981) (=  North-Holland Mathematics Studies ) . tape 75 . North-Holland, 1983, p. 131-141 , doi : 10.1016 / S0304-0208 (08) 73380-2 .
5. ^ Roland Häggkvist, Robert Johansson: A note on edge-decompositions of planar graphs . In: Discrete Mathematics . tape 283 , no. 1–3 , 2004, pp. 263-266 , doi : 10.1016 / j.disc.2003.11.017 .
6. ^ Gopi Meenakshisundaram, David Eppstein: Single-strip triangulation of manifolds with arbitrary topology . In: Computer Graphics Forum . tape 23 , 2004, pp. 371-379 , doi : 10.1111 / j.1467-8659.2004.00768.x , arxiv : cs.CG/0405036 .
7. ↑ László Lovász , Michael D. Plummer: Matching Theory (=  Annals of Discrete Mathematics . Volume 29 ). North-Holland, 1986, ISBN 0-444-87916-1 .
8. ^ Marc Voorhoeve: A lower bound for the permanent of certain (0,1) -matrices . In: Indagationes Mathematicae . tape 82 , no. 1 , 1979, p. 83-86 , doi : 10.1016 / 1385-7258 (79) 90012-X .
9. ^ Maria Chudnovsky , Paul Seymour : Perfect matchings in planar cubic graphs . In: Combinatorica . tape 32 , no. 4 , 2012, p. 403-424 , doi : 10.1007 / s00493-012-2660-9 .
10. ↑ Louis Esperet, František Kardoš, Andrew D. King, Daniel Král ', Serguei Norine: Exponentially many perfect matchings in cubic graphs . In: Advances in Mathematics . tape 227 , no. 4 , 2011, p. 1646–1664 , doi : 10.1016 / j.aim.2011.03.015 .
11. ^ Therese C. Biedl, Prosenjit Bose, Erik D. Demaine , Anna Lubiw: Efficient algorithms for Petersen's matching theorem . In: Journal of Algorithms . tape 38 , no. 1 , 2001, p. 110-134 , doi : 10.1006 / jagm.2000.1132 .
12. ↑ Mikkel Thorup : Near-optimal fully-dynamic graph connectivity . In: Proc. 32nd ACM Symposium on Theory of Computing . 2000, p. 343-350 , doi : 10.1145 / 335305.335345 .
13. ^ Krzysztof Diks, Piotr Stanczyk: Perfect matching for biconnected cubic graphs in time ${\displaystyle O(n\log ^{2}n)}$ . In: Jan van Leeuwen, Anca Muscholl, David Peleg, Jaroslav Pokorný, Bernhard Rumpe (eds.): Proceedings SOFSEM 2010: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010 (=  Lecture Notes in Computer Science ). tape 5901 , 2010, p. 321-333 , doi : 10.1007 / 978-3-642-11266-9_27 .