Petersen's theorem

Last updated
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.
A cubic (but not bridgeless) graph with no perfect matching, showing that the bridgeless condition in Petersen's theorem cannot be omitted Sylvester counter.svg
A cubic (but not bridgeless) graph with no perfect matching, showing that the bridgeless condition in Petersen's theorem cannot be omitted

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:

Contents

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching. [1]

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 G = (V, E) we have that for every set UV 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 the Tutte theorem G contains a perfect matching.

Let Gi be a component with an odd number of vertices in the graph induced by the vertex set V  U. Let Vi denote the vertices of Gi and let mi denote the number of edges of G with one vertex in Vi and one vertex in U. By a simple double counting argument we have that

where Ei is the set of edges of Gi with both vertices in Vi. Since

is an odd number and 2|Ei| is an even number it follows that mi has to be an odd number. Moreover, since G is bridgeless we have that mi  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  3|U|. We get

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

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 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 log4n) 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 log4n) 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 log2n) 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]

See also

Notes

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

Related Research Articles

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

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.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

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. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

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).

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

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.

<span class="mw-page-title-main">Snark (graph theory)</span> 3-regular graph with no 3-edge-coloring

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.

<span class="mw-page-title-main">Cubic graph</span> Graph with all vertices of degree 3

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.

<span class="mw-page-title-main">Bridge (graph theory)</span> Edge in node-link graph whose removal would disconnect the graph

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.

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

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

<span class="mw-page-title-main">Factor-critical graph</span> Graph of n vertices with a perfect matching for every subgraph of n-1 vertices

In graph theory, a mathematical discipline, a factor-critical graph is a graph with n vertices in which every induced 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 in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

<span class="mw-page-title-main">Claw-free graph</span> Graph without four-vertex star subgraphs

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">Hypohamiltonian graph</span> Type of graph in graph theory

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

<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.

<span class="mw-page-title-main">Hamiltonian decomposition</span>

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.

<span class="mw-page-title-main">Well-covered graph</span> Graph with equal-size maximal independent sets

In graph theory, a well-covered graph is an undirected graph in which the minimal vertex covers all have the same size. Here, a vertex cover is a set of vertices that touches all edges, and it is minimal if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs 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.

In the mathematical discipline of graph theory, the 2-factor theorem, discovered by Julius Petersen, is one of the earliest works in graph theory. It can be stated as follows:

Let G be a regular graph whose degree is an even number, 2k. Then the edges of G can be partitioned into k edge-disjoint 2-factors.

<i>The Petersen Graph</i>

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, ISBN   978-0-444-86512-0, 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 log2n) 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, ISBN   978-3-642-11265-2
  • 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, JSTOR   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