2-factor theorem

Theorem in graph theory 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:lovasz Let be a regular graph whose degree is an even number, . Then the edges of can be partitioned into edge-disjoint 2-factors. Here, a 2-factor is a subgraph of 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 -regular graph into two -factors.mulder 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 of such that every point has indegree and outdegree . Next, replace every vertex by two vertices and , and replace every directed edge of the oriented graph by an undirected edge from to . Since has in- and outdegrees equal to the resulting bipartite graph is -regular. The edges of can be partitioned into perfect matchings by a theorem of Kőnig. Now merging with for every recovers the graph , and maps the perfect matchings of onto 2-factors of which partition its edges.lovasz 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.lst See also Petersen's theorem – every 3-regular bridgeless graph contains a 2-factor References Lovász László Plummer M.D. 2009 Matching Theory American Mathematical Society 978-0-8218-4759-6. Lützen J. Sabidussi G. Toft B. 1992 Julius Petersen 1839–1910 a biography Discrete Mathematics 100 1–3 9–82 10.1016/0012-365X(92)90636-T free . Mulder H. 1992 Julius Petersen's theory of regular graphs Discrete Mathematics 100 1–3 157–175 10.1016/0012-365X(92)90639-W free . Category:Theorems in graph theory