On the face touching number
Daniel P. Sanders · Journal of Graph Theory · 1996
In a 3-connected plane graph, each pair of faces meet at at most either a vertex or an edge. Zha considered 3-connected graphs embedded on the projective plane, torus, and Klein bottle, showing that they meet at at most two, at most four, and at most four vertices or edges, respectively, and demonstrated graphs that showed that these bounds were best possible. He asked the question on what the maximum number of times two faces can meet on a general surface. This paper solves that problem, showing that two faces of a graph embedded on a non-planar surface of Euler characteristic ϵ meet at most 4–2ϵ times. The proof uses the Discharging Method, and seems to be the first application of this method to a problem which is wholly about graph embeddings. Also, graphs are demonstrated to show that this result is best possible. © 1996 John Wiley & Sons, Inc.