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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Isn't this identical to the other question you just asked? mathoverflow.net/questions/151802/… $\endgroup$
    – Gerry Myerson
    Commented Dec 14, 2013 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
    Commented Dec 14, 2013 at 5:19

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Dec 15, 2013 at 14:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .