I would appreciate a simpler explanation of the following info
I am confused on what the definition of 2-factor is. It sounds like a perfect matching to me, but that's not what this paper is saying
[Math] Definition of 2-factorable Graph Theory
graph theory
Related Solutions
Assume that $G$ is connected and has a perfect matching $M$. Weight the edges of $G$ by assigning weight $1$ to each edge in $M$ and weight $2$ to each edge not in $M$. Now apply Kruskal’s algorithm to find a minimal weight spanning tree $T$ for $G$. Kruskal’s algorithm will automatically include in $T$ all of the edges of $M$, so $M$ will be a perfect matching for $T$ as well.
As others have noted, if $G$ is not connected, it can’t have a spanning tree at all, and the assertion is trivially false.
There's no such pairing:
Observe that when you remove the $12$ red vertices, the graph splits into $14$ components, each of them having an odd number of vertices.
If there was a perfect pairing, each of the components would have a pair connecting it to some red vertex, but there's too few of them.
This condition on odd components in fact characterizes perfect pairings and it's called the Tutte theorem.
Best Answer
Ordinarily... a $k$-factor is a $k$-regular spanning subgraph. Thus
A $1$-factor is a perfect matching.
A $2$-factor will be a spanning subgraph which is a union of disjoint cycles.
This is the ordinary definition used in, say, Petersen's $2$-factor Theorem.
So here's an example of a graph with a $2$-factor highlighted as colored cycles:
A $k$-factorization is a decomposition into $k$-factors. A graph is $k$-factorable if it admits a $k$-factorization.
The above graph isn't $2$-factorable because it has vertices of odd degree.
Judging from the (now deleted) definition, the author:
includes isolated edges as $2$-cycles, and
defines a graph as "$2$-factorable" if there exists a $2$-factor for which after contracting the cycles, we obtain another graph with a $2$-factor.
According to this definition, a $1$-factor (perfect matching) would also be a $2$-factor. And the above graph would be $2$-factorable.
I've never seen this definition before.