Does the graph have a Hamiltonian circuit or a Hamiltonian path?

84 Views Asked by At

Graph that is to be assessed

Certain necessary conditions for a Hamiltonian circuit such as the graph being 2-connected, having zero pendants are met. Dirac's and Ore's theorem provide sufficient conditions, which are not satisfied by this graph, so it may possibly not be a Hamiltonian circuit. But as they are not necessary conditions, we can't yet conclude that this is not a Hamiltonian circuit. To me it seems that this graph does not contain a Hamiltonian circuit, as the entrances to the inner subgraphs have 2-degree vertices as their neighbours, then those edges must be traversed, similarly if we start from the inside of the subgraph, same situation occurs. But I cant put together a coherent formal argument for it.

In case of Hamiltonian path, the same thing happens, and I also cannot write it out properly. What way should I go about to argue in detail that this graph does not contain a Hamiltonian path or a circuit?

An additional query is, in this graph must only 2-degree vertices be the end vertieces of a path? Why?

1

There are 1 best solutions below

3
On

More detailed hints than in the comments.

Why there is no Hamiltonian path in this graph.

For convenience, let the vertices of degree 2 be red. Let the other vertices be blue.

First, note that the red vertices in each path cannot be neighbors, since they form an independent set.

It follows that if a Hamiltonian path starts with a blue vertex, then since there are $8$ red vertices, this path must also end with a blue vertex. Question: Where is the location of vertex $p$?

Let a Hamiltonian path start from a red vertex. In this case it is from the inner square (why?). By the same reasoning, there should be two blue vertices at the end of this path, and the last one is $p$.

Now find the first vertex on the Hamiltonian path from the outer square. It is preceded by a vertex from the small square. So they are both blue (why?).

Addition.

I will try to answer the OP's question from the comment below.

Recall that since the graph is bipartite and the parts have 8 and 9 elements, a Hamiltonian cycle can only start in the larger part. By the way, here are its parts: $aceg\ ojqm$; $bdfh\ ikln\ p$.

If a Hamiltonian cycle starts from a red vertex, then this red vertex is a larger part. The red vertices of the larger part all lie in a inner square. This is the answer to the first question.

Now to the second question. If we started our path in the inner square and set a goal of going around all the vertices of the graph, then somewhere along the way we will be in the outer square for the first time. Isn't that right?