Alexander Souza has offered for review on arXiv a constructive solution in the affirmative.
http://arxiv.org/abs/1202.0569
Edit: Unless we are mistaken, the Petersen graph is a counterexample to Theorem 2. Furthermore there is an unresolved problem with Lemma 9.
Claimed solution in the affirmative
Alexander Souza has offered for review on arXiv a constructive solution in the affirmative.
http://arxiv.org/abs/1202.0569
Edit: Unless we are mistaken, the Petersen graph is a counterexample to Theorem 2. Furthermore there is an unresolved problem with Lemma 9.