# Is this graph $G$ 2-connected and non-hamiltonian? Does Fleischner's theorem apply to $G^2$?

More specifically, does the stronger statement apply (Georgakopoulos 2009)?

"If $G=(V,E)$ is a 2-connected ﬁnite graph and $x \in V(G)$, then $G^2$ has a Hamilton cycle whose edges at $x$ lie in $E(G)$."

I am not sure I understand that statement fully. In the graph $G$ below the line $ag$ (or some other grey line) does not lie in $E(G)$, and I assume the existence of Hamilton cycle requires that line in G^2.

I either proved Georgakopoulos wrong (yeah right) or misunderstood something badly. I got wrong the statement, hamiltonicity, definition of $G^2$, or something else.

The graph in question

$G$ (black) and $G^2$ (black and grey):

-
+1 interesting. BTW: What did you use to draw that? – draks ... Jan 14 '13 at 12:59
@draks... Illustrator CS2. Still having trouble making the letters look like letters in LaTeX ... – Ohto Nordberg Jan 14 '13 at 13:14

Theorem 1. If $G$ is a 2-connected finite graph and $x \in V(G)$, then $G^2$ has a Hamilton cycle whose edges at $x$ lie in $E(G)$.

What this means is the following. Let $x \in V(G)$ be a vertex incident with the edges $\{e_1,e_2,\ldots,e_k\}$ in $G.$ Then there exist a Hamiltonian cycle $C$ in $G^2$ such that the edges incident with $x$ in $C$ are in $\{e_1,e_2,\ldots,e_k\}.$

-
Guess I do need more clarification ... Say in this case, vertex $g \in V(G)$ is incident with the edges $fg \in E(G)$ and $gb \in E(G)$. There does exist Hamiltonian cycle $C=\{agbcdefa\}$ in $G^2$. Now the edge $ag$ is incident with g but is not in E(G). – Ohto Nordberg Jan 14 '13 at 13:26
@OhtoNordberg Yes. The statement does not claim that every Hamiltonian cycle has this property but that there IS such a cycle. And this is true since you can take $g \mapsto f \mapsto e \mapsto a \mapsto c \mapsto d \mapsto b \mapsto g$ and you see that it contains $fg$ as well as $bg$ – Jernej Jan 14 '13 at 13:40
Ok, so what the statement is saying, is that $C$ (or some Hamilton cycle of $G^2$) will have a vertex whose incident edges are all edges of $G$? – Ohto Nordberg Jan 14 '13 at 13:56
No. What it says is that if you fix a vertex $x \in G$ you can find such a Hamiltonian cycle $C$ of $G^2$ that the incident edges of $x$ in $C$ are also the incident edges of $x$ in $G$ that is, they are from $G$ – Jernej Jan 14 '13 at 14:03
Ok, now I get it, thanks! – Ohto Nordberg Jan 16 '13 at 15:36

The question has actually 3 parts, and here is answer to the two first ones.

The graph $G$ in question is 2-connected, because no two vertices can be separated by removing one vertex.

The graph $G$ is not hamiltonian. According to this paper (page 7 theorem 2), order of $S$ must be greater than or equal to the number of components of the graph $G-S$ for $G$ to be hamiltonian.

You can think of the proof inductively: when you remove a vertex from a circle, it either keeps the number of components same or adds precisely one component to the graph $G-S$. When you remove one more vertex, number of components increase only if the removed vertex is not adjacent to any previously removed vertex.

In graph $G$ when $S={f,b}$, number of components of the graph $G-S$ is 3, which is greater than $|S|=2$.

-