Skip to main content
added 126 characters in body
Source Link
David Eppstein
  • 18.6k
  • 2
  • 55
  • 127

According to this source, a graph with a unique 2-factor must have a degree-two vertex. The result is credited to

Jackson, Bill; Whitty, R. W. (1989), "A note concerning graphs with unique $f$-factors", J. Graph Theory 13 (5): 577–580, doi:10.1002/jgt.3190130507.

However I don't have subscription access to that paper to verify that it really says that. So anyway, yes, if this is all accurate, then graphs with $\delta\ge 3$ have a second 2-factor when they have one.

Added later: see comments below. Apparently when Handbook of Graph Theory quoted this result, they omitted an additional assumption required for this result, that the graph be 2-edge-connected. This is why one needs to check original sources.

According to this source, a graph with a unique 2-factor must have a degree-two vertex. The result is credited to

Jackson, Bill; Whitty, R. W. (1989), "A note concerning graphs with unique $f$-factors", J. Graph Theory 13 (5): 577–580, doi:10.1002/jgt.3190130507.

However I don't have subscription access to that paper to verify that it really says that. So anyway, yes, if this is all accurate, then graphs with $\delta\ge 3$ have a second 2-factor when they have one.

According to this source, a graph with a unique 2-factor must have a degree-two vertex. The result is credited to

Jackson, Bill; Whitty, R. W. (1989), "A note concerning graphs with unique $f$-factors", J. Graph Theory 13 (5): 577–580, doi:10.1002/jgt.3190130507.

However I don't have subscription access to that paper to verify that it really says that. So anyway, yes, if this is all accurate, then graphs with $\delta\ge 3$ have a second 2-factor when they have one.

Added later: see comments below. Apparently when Handbook of Graph Theory quoted this result, they omitted an additional assumption required for this result, that the graph be 2-edge-connected. This is why one needs to check original sources.

Source Link
David Eppstein
  • 18.6k
  • 2
  • 55
  • 127

According to this source, a graph with a unique 2-factor must have a degree-two vertex. The result is credited to

Jackson, Bill; Whitty, R. W. (1989), "A note concerning graphs with unique $f$-factors", J. Graph Theory 13 (5): 577–580, doi:10.1002/jgt.3190130507.

However I don't have subscription access to that paper to verify that it really says that. So anyway, yes, if this is all accurate, then graphs with $\delta\ge 3$ have a second 2-factor when they have one.