3
$\begingroup$

I'm seeking a simple graph $G$ of the following type:

  • It contains two disjoint copies of $K_6$ (the complete graph on 6 nodes), $H$ and $H'$ say.
  • Any one-factor of $G$ must contain either (a) a one factor of $H$ and no edges in $H'$ or (b) a one factor of $H'$ and no edges in $H$.
  • There exists a one-factor of $G$ that contains a one-factor of $H$.
  • There exists a one-factor of $G$ that contains a one-factor of $H'$.

Question: Does $G$ exist?

I'm also interested in the same problem with $K_6$ replaced by $K_{2n}$.

My motivation for this question comes from an attempt to rephrase a question about Latin squares as a question about one-factors.

Improve this question
$\endgroup$
4
  • $\begingroup$ Can this be done for $K_4$? ($K_2$ is easy: two opposite sides of a hexagon.) $\endgroup$
    – Noam D. Elkies
    Commented Mar 25, 2012 at 5:10
  • $\begingroup$ Actually, I'm not sure for $K_4$ either. ($K_6$ just happened to be the case I was looking at.) $\endgroup$
    – Douglas S. Stones
    Commented Mar 25, 2012 at 5:41
  • $\begingroup$ But you want both kinds of one-factors to exist, right? It's easy to construct a graph that only has (a) kind of factors. $\endgroup$
    – Zsbán Ambrus
    Commented Mar 25, 2012 at 8:25
  • $\begingroup$ Yes, you're right. I'll edit that in. $\endgroup$
    – Douglas S. Stones
    Commented Mar 25, 2012 at 8:48

1 Answer 1

Reset to default
7
$\begingroup$

Here is a proof that $G$ does not exist. Let $M_1$ be a (red) 1-factor which contains a 1-factor $M_1'$ of the first $K_6$, and $M_2$ be a (blue) 1-factor which contains a 1-factor $M_2'$ of the second $K_6$. Note that $M_1 \triangle M_2$ is a union of even cycles, with alternating red and blue edges. Observe that we can get a new 1-factor by 'flipping' the edges on any such cycle. Therefore, there must be a cycle $C$ of $M_1 \triangle M_2$ which contains all the edges of $M_1' \cup M_2'$, otherwise we violate the second condition. Let $e \in E(C) \cap E(M_1')$. Traverse $C$ clockwise and let $f$ be the next edge of $C$ which is also in $E(M_1')$. Let $P$ be the subpath of $C$ beginning at $e$ and ending at $f$. Note that there is an edge $g$ between the ends of $P$ because of the first $K_6$. Therefore, if we flip the edges of $M_1$ along the even cycle $P \cup g$, we get another 1-factor. However, the intersection of this 1-factor with the first $K_6$ is neither empty nor a 1-factor.

Note that this proof works for any $K_{2n}$ for $n \geq 2$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That's a nice proof! (and seems to work for n=2 too) $\endgroup$
    – Douglas S. Stones
    Commented Mar 25, 2012 at 10:25
  • $\begingroup$ Yes, now that I think about it, the proof also works for $n=2$ since the constructed 1-factor will contain exactly one edge from the first $K_4$. $\endgroup$
    – Tony Huynh
    Commented Mar 25, 2012 at 10:38
  • $\begingroup$ I edited a 3 into a 2 accordingly. $\endgroup$
    – Tony Huynh
    Commented Mar 25, 2012 at 13:53

You must log in to answer this question.

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