Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-30T19:07:59.874Z Has data issue: false hasContentIssue false
  • English
  • Français

A Non-Hamiltonian Graph

Published online by Cambridge University Press:  20 November 2018

W. T. Tutte
W. T. Tutte*
Affiliation:
University of Toronto
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

There is a remarkable cubic graph of 28 vertices, discovered by Prof. H.S.M. Coxeter, which has no circuit of fewer than 7 edges and in which all oriented arcs made up of three edges are equivalent under the automorphism group.

The structure of the graph is as follows. There are three disjoint heptagons A(a1a2a3a4a5a6a7a1), B(b1b5b2b6b3b7b4b1) and C(c1c6c4c2c7c5c3c1). We denote the seven remaining vertices by d1, d2,…, d7. For each suffix i the three edges incident with dijoin it to ai, bi and ci. In drawing a diagram of the graph it seems best to show only the heptagons A, B and C, leaving the rest of the figure to the imagination.

The purpose of this note is to establish another property of the graph, that it has no Hamiltonian circuit.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 3 , Issue 1 , 01 January 1960 , pp. 1 - 5
Copyright
Copyright © Canadian Mathematical Society 1960