1
$\begingroup$

I have not too much experience with graph theory, so I am basically asking if someone knows if the answer to the following question follows from some theorem of graph theory (which I'm probably unaware of):

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a finite and simple graph with the following properties:

  1. It is bipartite.
  2. It is $3$-valent and admits a proper $3$-edge colouring, i.e. we can colour all edges by $3$ colours such that the $3$ edges adjacent to some vertex have different colours.
  3. It is spherical, i.e. $\vert\mathcal{F}\vert-\vert\mathcal{E}\vert+\vert\mathcal{V}\vert=2$, where $\mathcal{F}$ is the set of "faces", i.e. the set of all the bi-coloured cycles (=maximal connected components of two colours). It is actually a well-known fact from "crystallization theory" that this is equivalent to saying that the graph can be drawn in such a way that is planar and such that all the faces of the graph (=closed paths enclosing some area) are actually also "faces" in the sense defined above, i.e. the only consist of $2$ colours.

Under these assumptions, does there exists a closed path in the graph which is maximal in the sense that it touches every vertex of $\mathcal{G}$ exactly once?

I think graphs with these properties are called Hamiltonian in the graph theory literature. If this has any relevance, note that the graph $\mathcal{G}$ is actually balanced bipartite, which follows by combining bipartitness and the fact that it admits a proper edge colouring.

EDIT: I just found on the internet that what I am trying to prove for a few days now is very similar to what is called "Barnette's conjecture". So, I guess the question might be much harder then I thought^^

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This is not true unless you put further restrictions (e.g. connectivity) on the graph.

The graph below satisfies all your assumptions but it has no Hamiltonian cycle because any cycle containing an edge of a certain colour incident to the top vertex also contains the edge of the same colour incident to the bottom vertex.

graph

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, thats indeed I nice counter-example. In fact, you can find a simpler one when you just delete the six vertices which you have in-between each of the three columns. Then you end up with a graph which has in total 8 vertices, satisfying my assumptions, which has no Hamiltonian cycle. $\endgroup$
    – B.Hueber
    Commented Aug 2, 2022 at 15:19
  • $\begingroup$ not sure which vertices you are suggesting to delete, but I don't think 8 vertices are enough - the only balanced bipartite, 3-regular graph on 8 vertices is $K_{4,4}$ minus a matching (which is isomorphic to the 3-cube), and this graph has a Hamiltonian cycle $\endgroup$
    – Florian Lehner
    Commented Aug 2, 2022 at 19:58

You must log in to answer this question.

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