2-factor theorem

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

2-factor theorem. 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.[1]

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 outdegree 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 recover 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 in fact, one of the first results in 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 trial or a path alternatingly red and blue, and then to use the edges of one or both colours for the construction of other paths or trials.[3]

gollark: I think I saw an inbreeding coefficient calculator at some point.
gollark: Now to name one *The* Dragon of Orangeness.
gollark: And there's no way to contact the person.
gollark: Trading Hub being, as ever, annoying: I saw a trade for basically what I want (CB Chrono Xenowyrm) but there's an extra egg there which I can't accept.
gollark: Also, 4. it's quite easy to not cause yourself with some experience, but negatively affects new players most.

References
  1. Lovász, László, and Plummer, M.D.. Matching Theory, American Mathematical Soc., Jan 1, 2009. Print
  2. Mulder, H. "Julius Petersen’s theory of regular graphs". Discrete Mathematics, 100 (1992) 157-175 North-Holland
  3. Lützen, J.; Sabidussi, G. and Toft, B. (1992). "Julius Petersen 1839–1910 a biography". Discrete Mathematics, 100 (1–3): 9–82
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.