JOURNALOF COMBINATORIALTHEORY" 3, 326-365 (1967) Fastpl~ittbare G raphen K. WAGNER University KSln, Germany Communicated by G. Uhlenbeck ABSTRACT Let a be any vertex of a graph G. By deletion of a and of all those edges of G which are incident with a, we obtain the subgraph G/a of G. If G is nonplanar, but all subgraphs G/a of G are planar, then we call G nearly planar. We remark that every nearly planar graph is necessarily finite. Main result: All nearly planar graphs are determined explicitly. Let ~ be the class of all nearly planar graphs. Especially, ~ is composed of 4 different subclasses. For example, one subclass (without just 3 graphs) consists of all the non- planar graphs which can be embedded in the Mtibius strip in such a way that the border of the M6bius strip is always a Hamilton line of these graphs. Another subclass contains exactly the nonplanar graphs that consist of a path together with a circuit as disjoint subgraphs and of at most yet such edges which combine any vertex of the circuit with any end-point of the path. Further we show for every nearly planar graph that its chromatic number is never greater than 5. Moreover, we prove the theorem that the chromatic number of a nearly planar graph G is equal to 5 if and only if G is isomorphic to a graph K~ * C~ with an odd number n ~> 3, where K2 is an edge with its two vertices, C~ being disjoint to Kz is a circuit with n vertices, and the operation * means that every vertex of/(2 is combined by an edge with every vertex of C~. EINLEITUNG Sei G ein Graph und sei a eine Ecke yon G. Dann bedeutet G/a den- jenigen Teilgraphen von G, der aus G durch Streichung von a samt aller mit a inzidenten Kanten yon G entsteht. Ist k
