Skip to main content
2 of 2
top-level tag
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38

A Different 2-factor in a graph

We know that a k-factor of G is a k-regular spanning subgraph of G. And if G is 4-regular (or 2k-regular), it can be partitioned into 2 (k) edge-disjoint 2-factors (Petersen 1891).

My question is in a graph G with $\delta \geq 4$ which already has a 2-factor, can we say it has another 2-factor (different in at least one edge, not distinct)?

Mohemnist
  • 400
  • 1
  • 8