8
$\begingroup$

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)?

Improve this question
$\endgroup$
1
  • 8
    $\begingroup$ Wow, some people here with moderator privileges must really hate combinatorics. Else why vote to close this question, which is obviously research-level in graph theory? $\endgroup$
    – David Eppstein
    Commented Oct 26, 2015 at 6:36

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ I have access to Wiley Library, but unfortunately, pages 578 and 579 of this note are missing. This note has the total of 4 pages, so I have access to Page 1 and references!!!!!! $\endgroup$
    – Mohemnist
    Commented Oct 26, 2015 at 9:35
  • 1
    $\begingroup$ The first page does state the Theorem in question: Let $G$ be a 2-edge connected graph and $f:V(G)\to Z^+$. If $G$ has a unique $f$-factor, then some vertex $x$ of $G$ satisfies $d_G(x)=f(x)$. Fortunately, our library has a paper copy of the Jackson-Whitty paper, so I could scan the two missing pages if you need to see them. $\endgroup$
    – Timothy Chow
    Commented Oct 27, 2015 at 2:21
  • $\begingroup$ @TimothyChow It will be very helpful, if you scan the two pages and send it to me. You can send it to my username [at] gmail dot com. I also have a counterexample for the $\delta=3$ case. I've read in a survey that the 2-edge connectivity for the result of Jackson and Whitty is necessary. If I have access to these two pages I can confirm that. Thank you for your help. $\endgroup$
    – Mohemnist
    Commented Oct 27, 2015 at 20:18
  • 1
    $\begingroup$ I have posted the article on my website here. $\endgroup$
    – Timothy Chow
    Commented Oct 28, 2015 at 20:20
1
$\begingroup$

This proof is credited to Kamyar Khosravi.

We can orient the edges of graph $G$ such that $d_G^-(v), d_G^+(v)\geq 2$ for each $v\in V(G)$ and any cycle of the given 2-factor $F$ will become directed cycles. (We just orient the cycles of the given 2-factor and then orient the remaining edges, using one (or some) eulerian circuit for $v+G\backslash E(F)$ which $v$ is a new vertex connected to odd vertices of G).

Then we construct a bipartite graph $H$, each part $X$ and $Y$ having a copy of $V(G)$ and for any directed edge $e=uv$ in directed version of $G$ we add an edge from $u_X$ to $v_Y$. Each matching in H corresponds to a directed 2-factor in directed G. So by using edges of F, we can say H has a matching and satisfy Hall's condition. Then by an extended version of Hall's Theorem, we can say H has at least $\delta(X)!$ (if $\delta(X) < |X|$) which is $2!$ or simply $2$. So $G$ has at least two 2-factos. $\blacksquare$

For the case of $\delta(G)=3$ we can construct a counterexample graph with 18 vertices shown below. This graph has a cut edge $e=uv$, thus $e$ cannot be in any 2-factor. $u$ and $v$ must be in a triangle. We can then say other cycles of 2-factor are uniquely determined.

Counter example for the case of $\delta(G)=3$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .