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