MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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").

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
Very nice (and straightforward) application of Halls Theorem! Thank you. – Roland Bacher May 12 '11 at 16:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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