March 19, 1965

Dr. W. T. Tutte
Department of Mathematics
University of Toronto
Toronto, Ontario

Canada

Dear Dr. Tutte:

I have been interested for some time in an application of graph theory to
chemical structures. The enclosed materials may help to illustrate the direc-
tion of this work.

Part II of the DENDRAL report will be a tabulation of cyclic trivalent graphs
through 12 vertices, with some remarks on larger graphs, e.g., the listing of
the 16- and 18-vertex polyhedra lacking triangles. As the report may not be
so readily accessible to mathematicians I wondered about the utility of pub-
lishing this remark as a separate note. Could you suggest what might be an
appropriate journal for it?

The Hamiltonian circuits, when present, afford a convenient notation for coding
the graphs (as chord lists rotated, etc., to a minimal value). The non-polygonal
graphs are much more awkward. I have been looking at them as unions of subgraphs
on @ least polyhedron. The limiting case is the Hamiltonian circuit, when the
underlying "polyhedron" is a cirele. I did not know whether this generalization
of the Hamiltonian circuit has been thought of before; it might be useful for
other computational problems, as it is for the classification of these graphs.

In effect, any subgraph through which a path can be found is labelled (replaced
by an edge). The labels can then be mapped as a unique figure of lower order.
(I have no proof this is tnique, but I so far see no difficulty with a construc-
tive algorithm: reduce any path to a marked edge. In any further reductions if
@ path traverses a node incident on a marked edge it can be reduced only if it
includes themarked edge.)

I do not find this very elegant, and any alternative suggestions you may have
for a fundamental classification (and systematic construction) of such graphs
would be very helpful.

Indeed, I would appreciate comments or suggestions you may have at any point.

I would also be grateful for reprints of any of the many interesting papers you
have written in this field. I am constantly running into more of these, and

if you have a completelist of your works it would be helpful.

Sincerely yours,

Joshua, Lederberg
Professor of Genetics