Skip to main content
MathOverflow

Return to Answer

added counterexample for a 4-connected graph
Source Link
Wolfgang
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

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

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.

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.

minor
Source Link
Wolfgang
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

For a 3-connected counterexample, you can also take a 'truncated' PetersonPetersen graph, truncating meaning that we remplace each vertex of $Pete$ by a small'small' triangle (think of a truncated cube). Then aan induced cycle $G[V_1]$ as above must hit each triangle and thusmoreover alternate between triangle edges and edges of the original $Pete$. TheThus 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.

For a 3-connected counterexample, you can also take a 'truncated' Peterson graph, truncating meaning that we remplace each vertex of $Pete$ by a small triangle (think of a truncated cube). Then a cycle $G[V_1]$ must hit each triangle and thus alternate between triangle edges and edges of the original $Pete$. 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.

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.

Source Link
Wolfgang
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

For a 3-connected counterexample, you can also take a 'truncated' Peterson graph, truncating meaning that we remplace each vertex of $Pete$ by a small triangle (think of a truncated cube). Then a cycle $G[V_1]$ must hit each triangle and thus alternate between triangle edges and edges of the original $Pete$. 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.