K 44 Gamma e Has No Finite Planar Cover.pdfVIP

K4;4e Has No Finite Planar CoverPetr HlinenyDept. of Applied Mathematics, Charles University,Malostr. nam. 25, 118 00 Praha 1, Czech republic(E-mail: hlineny@kam.ms.mff.cuni.cz)September 4, 1997Abstract. A graph G has a planar cover if there exists a planar graph H, and a homo-morphism : H ! G that maps the neighbours of each vertex bijectively. Each graphthat has an embedding in the projective plane also has a nite planar cover. Negamiconjectured the converse in 1988.This conjecture holds as long as no minor-minimal non-projective graph has a nite planarcover. From the list there remain only two cases not solved yet|the graphs K4;4 e andK1;2;2;2. We prove the non-existence of a nite planar cover of K4;4e.1 IntroductionWe consider the following generalization of planarity of graphs: the planar covering of graphs.A planar graph H covers a graph G if there exists a graph homomorphism from H to Gsuch that for each vertex v of H its neighbours are mapped bijectively to the neighbours of(v). The set 1(v) is called the ber above v. If G is connected (and H is nite), then thesize of each ber is a constant called the fold number of the covering, and the cover is calledk-fold where k is the fold number.Every planar graph has a 1-fold planar cover by de nition, and every graph has an in niteplanar cover by an in nite tree. As a non-trivial example we mention a 2-fold planar cover ofnon-planar K5 (see the right-hand side of Figure 1), obtained from its projective drawing. ZZ ZZBBBBBr r r r r ZZ ZZBBBBBr r r r r r rrr r 1 2 34 5 12 3 45r rrr r12 3 451 2 34 5 + -Fig. 1. A 2-fold planar cover of K5, constructed from two copies of its projective drawingThis method can be easily generalized as follows: Suppose a graphG that has an embeddingin the projective plane, realized as a drawing in the normal plane with one cross-cap. Take thedrawing twice, and replace the edges going through the cross-caps by new edges connectingthe vertices of one copy to t