Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
    
Very nice (and straightforward) application of Halls Theorem! Thank you. –  Roland Bacher May 12 '11 at 16:07
add comment

Your Answer

 
discard

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.