A COMPLEMENTARY PROBLEM ON NONPLANAR GRAPHS,
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1962
- Accession Number
- AD0604458
Entities
People
- Frank Harary
Organizations
- RAND Corporation