March 31, 1975

x. Victor Kkee
Bepartment of Mathematics
University of Washington
Seattla, Washington 98105

Dear Victor,

Several times we have discussed possible intersections of deeper
mathematical analysis of graphs and our chemistry project. I told you at
one time that it was not a matter of urgent chemical necessity to know
the smallest non-Hamiltonian graphs, but I hope I did not leave the
impression that we felt we had solved all of our problems in that araal
While we think we have an adequate catalogue of graphs for the construction
of all possible molecules, we are still very much hampered by considerations
of efficiency - especially in finding the symmetry groups of arbitrary
constructions for labelling problems.

Y am enclosing some material that may help tell you where we stand
at the present time. I understand thera is some possibility that you may
be at the Center for Advanced Studies next year and if this is the case,
L certainly would hope we may have the opportunity for continued closer
interaction.

One issue has come up recently that you might be able to throw some
light on. Until now we have given little consideration to the tetrahedral
(specifically 44) symmetry of the carbon atom which is of course extrenely
important in considerations of stereo=iscmerism and the actual three-
dimensional conformation of molecules. We hope to incorporate this in the
near future.

In trying to patch in this capability into our existing system, it
occurred to us to ask what was the simplest trivalent graph that exhibited
A4. Coxeter and Moser have some brief discussion of this which you are
probably familiar with referring back to Kempe 1886. This is of course a
digraph and the simplest transformation of this into an undirected graph
is attached as my figure 1. In order to obtain useful vertices for simulating
the tetrahedral carbon atom, one would make constructions like Figure 2,

One can of course make Yetyly simple variations on these graphs to satisfy
particular restrictions like the absence of slings or whatever.

But I wanted to ask you if this is a subject that has been investigated
further and if it is known that there are no simpler solutions to this
questions: what is the simplest graph that displays Az? I would assume there
might also be some fairly interesting more general theory to connect rigid

~2-
Dr. Victor Mlee ~ 2 3/31/75

polyhedral with topological constructions. If you can point me to some
moderately elementary discussion of those connections, I would be most
appreciative.

The directed triangular subgraphs in Kempe’s diagram are of course a
surrogate for a particular kind of coloring of the nodes of the tatrahedron.
I do not know what more you might wish to make of that but I can assure you
thai: this would be of the greatest interest in the fornulazdzdmion of organic
molecular structure,

I think we can patch in the properties of the group Aq into our own
empirical pursuit of the labelling problem but {t would certainly be helpful
to have a sounder theoretical base than we have at the present time,

Connected with this is my previous remark that we can hardly be satisfied
with the present run time efficiency of thesa programs and I hope to have some
opportunity to discuss our strateggms in this area with you.

If it would be of any interest to you to become a collaborator for
investigating these problems on the SUMEX system, I would be more than
delighted to make the facility available to you. This does not have to
involve any vary formal commitment and if you would wish to do no more than
have some demonstration from your own home terminal of how these systems can
be run, we would be more than happy to afford this to you.

Sincerely yours,

Joshua Lederberg
Professor of Genetics

JL/rr
Enclosures