3
$\begingroup$

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$?

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

2 Answers 2

Reset to default
3
$\begingroup$

I believe this is false.

EDIT

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).

Improve this answer
$\endgroup$
6
  • $\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
    Commented Dec 15, 2013 at 6:39
  • $\begingroup$ @bof Thanks. In the several counterexamples found there are some vertex transitive. I stopped searching at order 16. $\endgroup$
    – joro
    Commented Dec 15, 2013 at 6:42
  • $\begingroup$ @joro thanks. I was wondering how you did your search. What software you are using? $\endgroup$
    – hbm
    Commented Dec 15, 2013 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
    Commented Dec 16, 2013 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
    Commented Dec 16, 2013 at 19:29
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think the Meredith graph is 4-regular 4-connected non-hamiltonian. $\endgroup$
    – joro
    Commented Dec 15, 2013 at 11:01

You must log in to answer this question.

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