
Accession Number : AD0604458
Title : A COMPLEMENTARY PROBLEM ON NONPLANAR GRAPHS,
Corporate Author : RAND CORP SANTA MONICA CALIF
Personal Author(s) : Harary,Frank
Report Date : FEB 1962
Pagination or Media Count : 7
Abstract : It has been found empirically by John L. Selfridge, in work with networks to be used as printed circuits, that for every network with nine nodes which was encountered, either it or its complementary network could not be printed with no intersecting arcs. In terms of graph theory this conjecture asserts that for every graph G with p = 9 points, either G or its complementary graph G is nonplanar. If this conjecture holds for graphs with 9 points, it clearly also holds for graphs with p > 9 points. It was remarked in the problem that a simple argument using Euler's polyhedron formula readily demonstrates the conjecture for all graphs having p > 11 points. The purpose of this miscellaneous note is to supply that argument.
Descriptors : (*GRAPHICS, THEORY), EULER ANGLES, EQUATIONS, THEOREMS, GEOMETRY, PRINTED CIRCUITS, NETWORKS
Distribution Statement : APPROVED FOR PUBLIC RELEASE