Non-separable and planar graphs

Abstract

Introduction.In this paper the structure of graphs is studied by purely combinatorial methods.The concepts of rank and nullity are fundamental.The first part is devoted to a general study of non-separable graphs.Conditions that a graph be non-separable are given ; the decomposition of a separable graph into its non-separable parts is studied; by means of theorems on circuits of graphs, a method for the construction of non-separable graphs is found, which is useful in proving theorems on such graphs by mathematical induction.In the second part, a dual of a graph is defined by combinatorial means, and the paper ends with the theorem that a necessary and sufficient condition that a graph be planar is that it have a dual.The results of this paper are fundamental in papers by the author on Congruent graphs and the connectivity of graphs^ and on The coloring of graphs.X