A SHORT PROOF OF THE PLANARITY CHARACTERIZATION OF DEVERDIERE,COLIN

Colin de Verdiere introduced an interesting new invariant mu(G) for graphs G, based on algebraic and analytic properties of matrices associated with G. He showed that the invariant is monotone under taking miners and moreover, that mu(G) less than or equal to 3 if only if G is planar. In this paper we give a short proof of Colin de Verdiere's result that mu(G) less than or equal to 3 if G is planar. (C) 1995 Academic Press, Inc.