Proof that 6 letters needs 8 nodes. Assume 7 nodes is possible. We can assume we are using a triangularized planar polyhedral graph. For 7 vertices, there are 5 such graphs. The degree sequences of the vertices are {{6,5,5,5,3,3,3},{6,6,4,4,4,3,3},{6,5,5,4,4,3,3},{5,5,5,4,4,4,3},{5,5,4,4,4,4,4}} Each has 15 edges, and we need 15 edges. But then we also need pairs of vertex degrees that add up to exactly 5, and that isn't possible. Plantri can generate planar graphs. http://cs.anu.edu.au/~bdm/plantri/ The next interesting case would be 7 letters. There are 50 9-node triangularized polyhedral graphs, each with 21 edges. For 8 letters, 28 edges are needed. 12 vertices are necessary, but these TP graphs have 30 edges. There are 7595 such graphs, and likely some of them would work. Finding the planar graphs that worked, after a plantri step, would be a programming exercise. --Ed Pegg Jr From: Allan Wechsler <acwacw@gmail.com> But what if we only need planarity? For five letters, I can do it with six nodes. For six letters I managed 8 nodes but couldn't prove that 7 was impossible. Thoughts?