2
$\begingroup$

Let $G$ be a $2$-connected $3$-regular graph. Is it true that $E(G) = E_1 \cup E_2$ where $G[E_1]$(the induced subgraph on $E_1$) is a cycle of $G$ and $G[E_2]$ is a forest (Acyclic subgraph) of $G$?

Edit:

Since the counterexamples presented so far are $2$-connected, what happen if the connectivity of the graph is $3$ instead of two?

$\endgroup$
  • $\begingroup$ Isn't this identical to the other question you just asked? mathoverflow.net/questions/151802/… $\endgroup$ – Gerry Myerson Dec 14 '13 at 3:42
  • $\begingroup$ Not quite. One deals with partitioning the edge set and the other with the vertex set. For example, in the edge case the cycle could have chord, however, in the vertex case the cycle cannot have a chord. $\endgroup$ – hbm Dec 14 '13 at 5:19
2
$\begingroup$

Let $G$ be the cubic graph on $30$ vertices obtained by replacing each vertex of the Petersen graph with a triangle. Then $G$ is $3$-connected because the Petersen graph is $3$-connected, and there is no cycle in $G$ that meets all ten triangles because there is no Hamiltonian cycle in the Petersen graph.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This method appears to work for the other question too. Found $G$ on $12$ vertices, 3-connected, non-hamiltonian. Replacing with a triangle gave a solution to the other problem. $\endgroup$ – joro Dec 15 '13 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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