Question regarding union of disjoint 1-factors

106 Views Asked by At

If a connected graph has two edge disjoint 1-factors, then the union of those two 1-factors is always a 2-regular spanning subgraph isn't it?

Moreover, when we consider a 2-regular spanning subgraph, which is formed by the union of two edge disjoint 1-factors and which is also a union of disjoint cycles rather than being a single cycle, then the cycles in the union should be of even length isn't it? Otherwise there will be an edge which does not belong to a disjoint union of 1-factors,right?

Can someone please help me with these two questions?

Thanks a lot in advance.

1

There are 1 best solutions below

1
On BEST ANSWER

If a connected graph has two edge disjoint 1-factors, then the union of those two 1-factors is always a 2-regular spanning subgraph isn't it?

Yes, this union is spanning and it is 2-regular, because each its vertex has exactly one incident edge from each of the 1-factors.

Moreover, when we consider a 2-regular spanning subgraph, which is formed by the union of two edge disjoint 1-factors and which is also a union of disjoint cycles rather than being a single cycle, then the cycles in the union should be of even length isn't it? Otherwise there will be an edge which does not belong to a disjoint union of 1-factors,right?

Right, because the set of edges of a cycle of odd length cannot be covered by two edge-disjoint matchings. Indeed, a first of these matchings covers an even number of vertices, so there remains a vertex $v$ of the cycle non-covered by it. Two cycle edges, incident to the vertex $v$ cannot both be covered by the second matching.