Merging of 2 1-factor leads to 2-factor?

149 Views Asked by At

I have a doubt on how if two 1-factor in a graph when merged becomes 2 factor. Context is - In a 2k regular graph, there is a 2 factor

In my book's proof, 2k regular graph --> split each vertex in to 2 vertices say $v^+, v^-$ such that edges goes from positive vertex to negative vertex. Since degree is even there is eulerian circuit. From this, we can have a k-regular bipartite graph. So we can have perfect matching or 1-factor. But then how can we say that merging of this 2 vertices again will lead of 2 factor.

1

There are 1 best solutions below

0
On

I don't know what book you're using, but you may want to refer to Introduction to Graph Theory by West, second edition, Pg $140$.

Theoreom (Due to Petersen): Every regular graph of even degree has a $2$-factor.

By $k$-factor we mean a $k$-regular spanning subgraph. (To make things simple let's assume $G$ is connected).

The essence of the proof is that if a graph $G$ is $2k$-regular, then there exists an Eulerian circuit $C$. If we orient $G$ with $C$, then we obtain a directed graph $D$ where every vertex is entered $k$ times and exited $k$ times (that is, $\deg^+(v) =\deg^-(v) \quad \forall v \in V(D)$). Now consider the split $D_s$ of $D$, which is a bipartite graph with vertex sets $V^+$ and $V^-$ (each set is a copy of $V(D)$), and for $u \in V^+$ and $w \in V^-$ we have $uw \in E(D_s)$ if $u \to w$ in $D$. Since every vertex is entered and exited $k$ times in $D$, it must be the case that $D_s$ is $k$-regular. By Hall's Theorem $D_s$ must have a perfect matching $M$, or a $1$-factor $F$.

Now to address your confusion. The $1$-factor in $D_s$ corresponds to a $2$-factor in $D$ (and consequently a $2$-factor in $G$). Why is this?

Well, $M$ is a perfect matching, so for every $u \in V^+$ there is exactly $1$ edge incident to $u$, and for every $w \in V^-$ there is exactly $1$ edge incident to $w$, and these edges each correspond to an edge in $D$. In other words, our $1$-factor $F$ of $D_s$ tells us that every vertex is entered exactly once and exited exactly once in $G' = (V(D),M)$. Remember, $F$ is a spanning subgraph and $M$ is a perfect matching, in this case $M = E(F)$.

In case you don't have a copy of West, the example given is: enter image description here where we have $K_5$ and take our Eulerian cycle to be $1231425435$. Can you work out this example and build the intuition?

As a final note, I believe you were getting confused in your drawings because you were trying to obtain a perfect matching in the split by just having an Eulerian graph, which is not sufficient (as Gregory J. Puleo points out.) The nice thing about being $2k$-regular is that our split will be guaranteed to have a perfect matching.

If I am not clear anywhere I will try and clarify. For now I sleep.