Abstract
A graph H is a cover of a graph G if there exists a mapping φ from V(H) onto V(G) such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ(υ) in G. Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. It follows from the results of Archdeacon, Fellows, Negami, and the author that the conjecture holds as long as K~1,2,2,2~ has no finite planar cover. However, this is still an open question, and K~1,2,2,2~ is not the only minor‐minimal graph in doubt. Let 𝒞~4~ (ℰ~2~) denote the graph obtained from K~1,2,2,2~ by replacing two vertex‐disjoint triangles (four edge‐disjoint triangles) not incident with the vertex of degree 6 with cubic vertices. We prove that the graphs 𝒞~4~ and ℰ~2~ have no planar covers. This fact is used in [P. Hlinĕný, R. Thomas, On possible counterexamples to Negami's planar cover conjecture, 1999 (submitted)] to show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 227–242, 2001