Petersen's theorem

Last updated October 05, 2023

A perfect matching (red edges), in the Petersen graph. Since the Petersen graph is cubic and bridgeless, it meets the conditions of Petersen's theorem. Petersen-graph-factors.svg — A perfect matching (red edges), in the Petersen graph. Since the Petersen graph is cubic and bridgeless, it meets the conditions of Petersen's theorem.

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:

Proof

We show that for every cubic, bridgeless graph $G = (V, E)$ we have that for every set $U \subseteq V$ the number of connected components in the graph induced by $V - U$ with an odd number of vertices is at most the cardinality of $U$ . Then by Tutte theorem $G$ contains a perfect matching.

Let $G i$ be a component with an odd number of vertices in the graph induced by the vertex set $V - U$ . Let $V i$ denote the vertices of $G i$ and let $m i$ denote the number of edges of $G$ with one vertex in $V i$ and one vertex in $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 $E i$ is the set of edges of $G i$ with both vertices in $V i$ . Since

\sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|

is an odd number and $2| E i |$ is an even number it follows that $m i$ has to be an odd number. Moreover, since $G$ is bridgeless we have that $m i \geq 3$ .

Let $m$ be the number of edges in $G$ with one vertex in $U$ and one vertex in the graph induced by $V - U$ . Every component with an odd number of vertices contributes at least 3 edges to $m$ , and these are unique, therefore, the number of such components is at most $m /3$ . In the worst case, every edge with one vertex in $U$ contributes to $m$ , and therefore $m \leq 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".^[1] By today's standards Petersen's proof of the theorem is complicated. A series of simplifications of the proof culminated in the proofs by Frink (1926) and 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.^[2]
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.^[3]
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.^[4]

Extensions

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 $n$ .^[5] The conjecture was first proven for bipartite, cubic, bridgeless graphs by Voorhoeve (1979), later for planar, cubic, bridgeless graphs by Chudnovsky & Seymour (2012). The general case was settled by Esperet et al. (2011), where it was shown that every cubic, bridgeless graph contains at least $2^{n/3656}$ perfect matchings.

Algorithmic versions

Biedl et al. (2001) discuss efficient versions of Petersen's theorem. Based on Frink's proof^[6] they obtain an $O (n log 4 n)$ algorithm for computing a perfect matching in a cubic, bridgeless graph with $n$ vertices. If the graph is furthermore planar the same paper gives an $O (n)$ algorithm. Their $O (n log 4 n)$ time bound can be improved based on subsequent improvements to the time for maintaining the set of bridges in a dynamic graph.^[7] Further improvements, reducing the time bound to $O (n log 2 n)$ or (with additional randomized data structures) $O (n log n (log log n) 3)$ , were given by 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.^[8]

Notes

1 2 Petersen (1891).
↑ See for example Bouchet & Fouquet (1983).
↑ Häggkvist & Johansson (2004).
↑ Meenakshisundaram & Eppstein (2004).
↑ Lovász & Plummer (1986).
↑ Frink (1926).
↑ Thorup (2000).
↑ Naddef & Pulleyblank (1981), Theorem 4, p. 285.

Related Research Articles

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite undirected graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs. It is a special case of the Tutte–Berge formula.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every subgraph of $n - 1$ vertices has a perfect matching.

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, 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 who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

<span class="mw-page-title-main">Tietze's graph</span> Undirected cubic graph with 12 vertices and 18 edges

In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors. The boundary segments of the regions of Tietze's subdivision form an embedding of Tietze's graph.

In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

<span class="mw-page-title-main">Apollonian network</span> Graph formed by subdivision of triangles

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.

The Petersen Graph is a mathematics book about the Petersen graph and its applications in graph theory. It was written by Derek Holton and John Sheehan, and published in 1993 by the Cambridge University Press as volume 7 in their Australian Mathematical Society Lecture Series.

References

Biedl, Therese C.; Bose, Prosenjit; Demaine, Erik D.; Lubiw, Anna (2001), "Efficient algorithms for Petersen's matching theorem", Journal of Algorithms, 38 (1): 110–134, doi:10.1006/jagm.2000.1132, MR 1810434
Bouchet, André; Fouquet, Jean-Luc (1983), "Trois types de décompositions d'un graphe en chaînes", in C. Berge; D. Bresson; P. Camion; J.F. Maurras; F. Sterboul (eds.), Combinatorial Mathematics: Proceedings of the International Colloquium on Graph Theory and Combinatorics (Marseille-Luminy, 1981), North-Holland Mathematics Studies (in French), vol. 75, North-Holland, pp. 131–141, doi:10.1016/S0304-0208(08)73380-2, MR 0841287
Chudnovsky, Maria; Seymour, Paul (2012), "Perfect matchings in planar cubic graphs", Combinatorica , 32 (4): 403–424, doi:10.1007/s00493-012-2660-9, MR 2965284
Diks, Krzysztof; Stanczyk, Piotr (2010), "Perfect matching for biconnected cubic graphs in $O(n log 2 n)$ time", in van Leeuwen, Jan; Muscholl, Anca; Peleg, David; Pokorný, Jaroslav; Rumpe, Bernhard (eds.), 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, Lecture Notes in Computer Science, vol. 5901, Springer, pp. 321–333, doi:10.1007/978-3-642-11266-9_27
Esperet, Louis; Kardoš, František; King, Andrew D.; Králʼ, Daniel; Norine, Serguei (2011), "Exponentially many perfect matchings in cubic graphs", Advances in Mathematics , 227 (4): 1646–1664, arXiv: 1012.2878 , doi: 10.1016/j.aim.2011.03.015 , MR 2799808
Frink, Orrin (1926), "A proof of Petersen's theorem", Annals of Mathematics , Second Series, 27 (4): 491–493, doi:10.2307/1967699
Häggkvist, Roland; Johansson, Robert (2004), "A note on edge-decompositions of planar graphs", Discrete Mathematics , 283 (1–3): 263–266, doi: 10.1016/j.disc.2003.11.017 , MR 2061501
König, Dénes (1936), Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe.
Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
Meenakshisundaram, Gopi; Eppstein, David (2004), "Single-strip triangulation of manifolds with arbitrary topology", Proc. 25th Conf. Eur. Assoc. for Computer Graphics (Eurographics '04), Computer Graphics Forum, vol. 23, pp. 371–379, arXiv: cs.CG/0405036 , doi:10.1111/j.1467-8659.2004.00768.x
Naddef, D.; Pulleyblank, W. R. (1981), "Matchings in regular graphs", Discrete Mathematics , 34 (3): 283–291, doi: 10.1016/0012-365X(81)90006-6 , MR 0613406 .
Petersen, Julius (1891), "Die Theorie der regulären graphs", Acta Mathematica , 15: 193–220, doi: 10.1007/BF02392606
Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing , pp. 343–350, doi:10.1145/335305.335345, ISBN 1-58113-184-4, MR 2114549
Voorhoeve, Marc (1979), "A lower bound for the permanents of certain (0,1)-matrices", Indagationes Mathematicae , 82 (1): 83–86, doi: 10.1016/1385-7258(79)90012-X , MR 0528221

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[p1891-1] 1 2 Petersen (1891).

[2] See for example Bouchet & Fouquet (1983).

[3] Häggkvist & Johansson (2004).

[FOOTNOTEMeenakshisundaramEppstein2004-4] Meenakshisundaram & Eppstein (2004).

[FOOTNOTELovászPlummer1986-5] Lovász & Plummer (1986).

[6] Frink (1926).

[FOOTNOTEThorup2000-7] Thorup (2000).

[8] Naddef & Pulleyblank (1981), Theorem 4, p. 285.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]