Some new polyhedra with vertex degree 4 and/or 5 only

A table of 4and 5-hedra of orders up to and including 22 is given. In 1981 we reported on the number of polyhedral graphs [5]. That work was a byproduct of the search for the lowest-order squared square, which was found in March 1978 [3]. The squaring problem is closely related to the theory of 3-connected planar graphs, as was first shown by Brooks, Smith, Stone, and Tutte [1] in 1940. In 1962 we developed the necessary techniques for computer manipulation of 3-connected planar graphs. These techniques were reported in [2]. The set of 4and 5-hedra is a subset of the set of 3-connected planar graphs. In that paper, a code for 3-connected graphs was introduced in which the essential properties of planarity are preserved. It is assumed that the graph is drawn on the sphere. The vertices are numbered arbitrarily from 1 to K, where K is the number of vertices of the graph. The sides or meshes are numbered arbitrarily from 1 to M, where M is the number of sides (or meshes). The boundary contains a set of vertices. A code of a side is obtained as follows: while walking in the positive sense along the boundary of the side, starting with Vi, we encounter Vj, Jk, VJ, ..., untilwe return to Vi . The sequence Vi, Vi, Vk, VI, ..., Vi is a code of the side. Example. A possible code of side 1 of the reference graph is 1 2 6 5 1, as can be seen from Figure 1; but we can also take 265 12, 65 126, or 5 1265. A code of the graph is the sequence of codes of all its sides, separated by zeros. At the end, two more zeros are added. Example. A code of the reference graph is as follows: 126510236203563034530154101432100 In case we deal with more than nine vertices, it is more convenient to code the vertices with (capital letters, where A = 1 , B = 2, C = 3, etc. Example. The above code of the reference graph reads: ABFEAOBCFBOCEFCOCDECOAEDAOADCBAOO Received May 8, 1989. 1980 Mathematics Subject Classification (1985 Revision). Primary 68R10, 05C99. ? 1990 American Mathematical Society 0025-5718/90 $1.00+ $.25 per page