A COMPLEMENTARY PROBLEM ON NONPLANAR GRAPHS,
RAND CORP SANTA MONICA CALIF
Pagination or Media Count:
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 Eulers polyhedron formula readily demonstrates the conjecture for all graphs having p 11 points. The purpose of this miscellaneous note is to supply that argument.