In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

discipline of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the 2-factor theorem, discovered by

Julius Petersen Julius Peter Christian Petersen (16 June 1839, Sorø, West Zealand – 5 August 1910, Copenhagen) was a Danish mathematician. His contributions to the field of mathematics led to the birth of graph theory. Biography Petersen's interests i ...

, is one of the earliest works in graph theory. It can be stated as follows: : 2-factor theorem. Let ''G'' be a

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...

whose degree is an even number, 2''k''. 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 2''k''-regular graph into two ''k''-factors. 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 Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building de ...

''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.^{/sup>

History

The theorem was discovered by Julius Petersen

Julius Peter Christian Petersen (16 June 1839, Sorø, West Zealand – 5 August 1910, Copenhagen) was a Danish mathematician. His contributions to the field of mathematics led to the birth of graph theory.
Biography
Petersen's interests i ...
, a Danish mathematician. It is one of the first results ever discovered in the field of graph theory

In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
. 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.Lützen, J.; Sabidussi, G. and Toft, B. (1992). "Julius Petersen 1839–1910 a biography". ''Discrete Mathematics'', 100 (1–3): 9–82

References

{{reflist

Theorems in graph theory}