# Questions about Hamiltonian Graph

Come up with an example of graphs:

• Graph $G$ without bridges and $G^2$ isn't Hamiltonian Graph.
• Graph $G$ is triconnected graph, local-connected (it means that for all vertices: the environment of a vertex (without itself) is connected graph) and $G$ isn't Hamiltonian Graph
• Graph $G$ is cubic graph, triconnected and $G$ isn't Hamiltonian Graph.
• Graph $G$ is connected, local-Hamiltonian (it means that for all vertices: the environment of a vertex (without itself) is Hamiltonian Graph), and $G$ isn't Hamiltonian Graph.

Why:

• If graph $G$ is connected, local-connected, edge-connected $\Rightarrow$ $G$ is Hamiltonian Graph.

Please give some examples or clues!

Thanks anyway!

-
By the environment of $v$ you mean the subgraph generated by the neighbors of $v$? –  Brian M. Scott Nov 30 '12 at 1:13
The first one seems impossible. The square of any biconnected graph is Hamiltonian. –  EuYu Nov 30 '12 at 1:21
Some thoughts: 1. seems impossible. See here 3. is given by the Petersen graph. 4. Every locally Hamiltonian graph is $3$-connected and locally connected so an example here will also suffice for 2. This reference suggests that the smallest example for will be of order $11$. "If graph $G$ is connected, local-connected, ..." I don't understand why you think the result is true, doesn't 2 and 4 both provide counter-examples to it? –  EuYu Nov 30 '12 at 3:07
@jofisher Oh of course. Silly mistake on my part. –  EuYu Nov 30 '12 at 5:46
The link is to a question on Overflow. The answer provides a link to a paper which contains a bridgeless graph whose square is non-Hamiltonian. You can view the graph by following the links and previewing the article. –  EuYu Nov 30 '12 at 6:33