Skip to main content
2 of 6
Briefly address also the second part of the question.
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

I assume removing a face means here: select a face, remove all its vertices and all their incident edges. (Otherwise I don't understand what happens to edges when one of their endpoints is removed.)

Then the answer is no. Some small counterexamples are Graph 226 and Graph 160 (House of Graph numbering). Pictures (courtesy of HoG) below. Removing the central face from each of them leaves a triangle and a square, respectively, so the vertex connectivity goes down to two in each case.

A six-vertex planar 4-connected graph An eight-vertex planar 4-connected graph


To the second part ("under what conditions is this true") I have no good answer, except that in small graphs it seems to be more commonly false. To wit, I used the plantri program (by Brinkmann, Van de Kamp and McKay, available here) to exhaustively generate planar 4-connected graphs. For each graph I chose an arbitrary planar embedding, and checked whether some face can be removed so that the remaining graph is 4-connected.

Here are some statistics, where #graphs counts the planar 4-connected graphs (OEIS A007027), and #face-removable counts those where such a face could be found:

vertices #graphs #face-removable
6 1 0
7 1 0
8 4 0
9 10 0
10 53 0
11 292 5
12 2224 35
13 18493 427

Here is one example of an 11-vertex graph where the condition is true (removing any face still leaves the graph 4-connected).

An 11-vertex planar 4-connected graph

Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49