2-factor theorem

Last updated

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: [1]

Contents

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.

Here, a 2-factor is a subgraph of G in which all vertices have degree two; that is, it is a collection of cycles that together touch each vertex exactly once.

Proof

In order to prove this generalized form of the theorem, Petersen first proved that a 4-regular graph can be factorized into two 2-factors by taking alternate edges in a Eulerian trail. He noted that the same technique used for the 4-regular graph yields a factorization of a 2k-regular graph into two k-factors. [2]

To prove this theorem, it is sufficient to consider connected graphs. A connected graph with even degree has an Eulerian trail. Traversing this Eulerian trail generates an orientation D of G such that every point has indegree and outdegree = k. Next, replace every vertex v ϵ V(D) by two vertices v’ and v”, and replace every directed edge uv of the oriented graph by an undirected edge from u’ to v”. Since D has in- and outdegrees equal to k the resulting bipartite graph G’ is k-regular. The edges of G’ can be partitioned into k perfect matchings by a theorem of Kőnig. Now merging v’ with v” for every v recovers the graph G, and maps the k perfect matchings of G’ onto k 2-factors of G which partition its edges. [1]

History

The theorem was discovered by Julius Petersen, a Danish mathematician. It is one of the first results ever discovered in the field of graph theory. The theorem appears first in the 1891 article "Die Theorie der regulären graphs". To prove the theorem, Petersen's fundamental idea was to 'colour' the edges of a trail or a path alternatively red and blue, and then to use the edges of one or both colours for the construction of other paths or trials. [3]

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.

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.

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

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">Degree (graph theory)</span> Number of edges touching a vertex in a graph

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph , denoted by , and the minimum degree of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

<span class="mw-page-title-main">Graph factorization</span>

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 graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is a proper edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph.

<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 subgraph of n − 1 vertices has a perfect matching.

In graph theory, a bivariegated graph is a graph whose vertex set can be partitioned into two equal parts such that each vertex is adjacent to exactly one vertex from the other set not containing it. In a bivarigated graph G with 2n vertices, there exists a set of n independent edges such that no odd number of them lie on a cycle of G.

<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">Odd graph</span> Family of symmetric graphs which generalize the Petersen graph

In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph.

<span class="mw-page-title-main">Grinberg's theorem</span> On Hamiltonian cycles in planar graphs

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.

Paul Allen Catlin was a mathematician, professor of mathematics who worked in graph theory and number theory. He wrote a significant paper on the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.

<span class="mw-page-title-main">Petersen's theorem</span>

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.

In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.

In the mathematical field of graph theory, a prism graph is a graph that has one of the prisms as its skeleton.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

References

  1. 1 2 Lovász, László; Plummer, M.D. (2009), Matching Theory, American Mathematical Society, ISBN   978-0-8218-4759-6 .
  2. ↑ Mulder, H. (1992), "Julius Petersen's theory of regular graphs", Discrete Mathematics, 100: 157–175, doi: 10.1016/0012-365X(92)90639-W .
  3. ↑ Lützen, J.; Sabidussi, G.; Toft, B. (1992), "Julius Petersen 1839–1910 a biography", Discrete Mathematics, 100 (1–3): 9–82, doi: 10.1016/0012-365X(92)90636-T .
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.