Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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

Please give some examples or clues!

Thanks anyway!

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.