Take the complete bipartite graph . Its seven vertices have degrees four on one side and three on the other. Deleting any two vertices leaves at least one vertex on each side, so the remaining complete bipartite graph is connected.
Every cycle in a bipartite graph alternates between its two parts, using equal numbers of vertices from each. A Hamilton cycle here would have to use three vertices from one part and four from the other, which is impossible. Thus three-vertex connectivity and minimum degree three do not suffice for Hamiltonicity in this seven-vertex example.

Ancestors (13)

  1. iii
  2. a
  3. 6
  4. 2014
  5. Past exam of the short options course of the University of Oxford
  6. Short options course of the University of Oxford
  7. Year 2 of the mathematics course of the University of Oxford
  8. Mathematics course of the University of Oxford
  9. Undergraduate course of the University of Oxford
  10. Course of the University of Oxford
  11. University of Oxford
  12. List of universities
  13. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version