Let $G$ be a $2$-connected $3$-regular graph. Can $V(G)$ be partitioned into $V_1$ and $V_2$ where $G[V_1]$(the induced subgraph on $V_1$) is a cycle of $G$ and $G[V_2]$ is a forest (Acyclic subgraph) of $G$?


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

  • $\begingroup$ Could you put back the answer I will accept it. I just was not sure about re-posting the question. $\endgroup$
    – hbm
    Dec 15 '13 at 2:57
  • $\begingroup$ In general, it's best not to change a question after a correct answer has been posted. $\endgroup$ Dec 16 '13 at 2:27
  • $\begingroup$ @FrançoisG.Dorais basically I agree with you, but this doesn't apply to typos/very minor corrections. $\endgroup$
    – joro
    Dec 16 '13 at 7:33

I believe this is false.


The previous counterexample was wrong, let me try again.

A program found counterexample on $10$ vertices and exhaustive search confirmed it.

The edges are:

[(0, 3), (0, 5), (0, 7), (1, 4), (1, 6), (1, 9), (2, 6), (2, 7), (2, 8), (3, 5), (3, 7), (4, 8), (4, 9), (5, 8), (6, 9)]

It is $2$-connected.

According to a search the smallest $3$-connected counterexample is on $12$ vertices with edges

[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 9), (2, 6), (2, 10), (2, 11), (3, 7), (3, 10), (3, 11), (4, 8), (4, 9), (4, 10), (5, 8), (5, 9), (5, 11)]

There are other counterexamples (modulo errors).

  • $\begingroup$ Nice example. (I mean the $3$-connected graph on $12$ vertices.) I haven't verified it, but it looks like it should work. To draw the graph neatly, draw a big circle around (not touching) a Star of David, and extend the lines in the star until they touch the circle, making six chords. The vertices of the graph are the points where the chords meet the circle. Of course the graph is Hamiltonian so it doesn't work for the other question. $\endgroup$
    – bof
    Dec 15 '13 at 6:39
  • $\begingroup$ @bof Thanks. In the several counterexamples found there are some vertex transitive. I stopped searching at order 16. $\endgroup$
    – joro
    Dec 15 '13 at 6:42
  • $\begingroup$ @joro thanks. I was wondering how you did your search. What software you are using? $\endgroup$
    – hbm
    Dec 15 '13 at 20:33
  • $\begingroup$ @hbm For this I used sage for computations and the optional package nauty for generating cubic graphs. Both of them are free. Basically generated cubic graphs, iterated over the induced cycles (builtin func.) and checked for a forest. The code is short, fast and easy to write with basic knowledge of sage. Contact me if you want the source. $\endgroup$
    – joro
    Dec 16 '13 at 7:09
  • $\begingroup$ @joro: I am new to sage. Could be kind and post the a copy of the source code. Thx $\endgroup$
    – hbm
    Dec 16 '13 at 19:29

For a 3-connected counterexample, you can take a 'truncated' Petersen graph, truncating meaning that we remplace each vertex of $Pete$ by a 'small' triangle (think of a truncated cube). Then an induced cycle $G[V_1]$ as above must hit each triangle and moreover alternate between triangle edges and edges of the original $Pete$. Thus the latter edges would form a Hamilton cycle of $Pete$, which doesn't exist.

Note that similar truncating constructions for higher connectivity $k>3$ won't work, as for $k=4$ a non Hamiltonian 4-regular 4-connected graph just doesn't exist (if my memory serves), and for $k>4$ a 'truncated vertex' $C_k$ might be visited more than once.

Edit after Soro's comment: Truncating the Meredith graph $M$ (i.e. replacing each vertex by a small $C_4$ - note that this can be done in 3 different ways for each vertex, but that isn't relevant) will result in a cubic graph with 280 vertices that is still 4-connected. If a cycle as above exists, it must hit each $C_4$ (sharing either one or two adjacent edges with it) and alternatingly with those, hit edges of $M$, which would again form a Hamilton cycle of $M$.

Just a feeling: for a $5$-connected graph, I would conjecture the statement to hold.

  • $\begingroup$ I think the Meredith graph is 4-regular 4-connected non-hamiltonian. $\endgroup$
    – joro
    Dec 15 '13 at 11:01

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.