A Complementary Problem on Nonplanar Graphs
Frank Harary · Mathematics Magazine · 1962
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.