6
$\begingroup$

Let $G=(V,E)$ be a finite simple $k-$regular graph ($k\geq 1$). Does $G$ necessarily contain a subset $E'\subset E$ of edges such that only isolated edges and cycles occur as connected components in $(V,E')$?

(The answer is easily yes for $k=1,2$.)

A counterexample would easily give a counterexample to question "Antipodal" maps on regular graphs? in the case $D=2$ by considering the complementary graph of $G$ (respectively of two disjoint copies of $G$ if $G$ is "too small").

$\endgroup$

1 Answer 1

6
$\begingroup$

It seems like such a subset should always exist.

Consider the bipartite graph on $2|V(G)|$ vertices corresponding to the adjacency matrix of $G$. Since this graph is regular, by Hall's Theorem it has a perfect matching. In terms of the original $G$, this corresponds to a permutation $\sigma$ on $V(G)$ such that $v$ and $\sigma(v)$ are always adjacent. The cycles of $\sigma$ would then give you the desired decomposition.

$\endgroup$
1
  • $\begingroup$ Very nice (and straightforward) application of Halls Theorem! Thank you. $\endgroup$ May 12, 2011 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.