Return to Answer

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 Graphs 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.

To the second part ("under what conditions is this true") I have no good answer, except that in small graphs it is more commonly false than true. To wit, I used the plantri program (by Brinkmann, Van den Camp 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:

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

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 Graphs 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.

To the second part ("under what conditions is this true") I have no good answer, except that in small graphs it is more commonly false than true. To wit, I used the plantri program (by Brinkmann, Van den Camp 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:

Here is one example of an 11-vertex graph where the condition is true (removing the $0,3,4$ face leaves the graph 4-connected).

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 Graphs 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.

To the second part ("under what conditions is this true") I have no good answer, except that in small graphs it is more commonly false than true. 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:

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

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 Graphs 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.

To the second part ("under what conditions is this true") I have no good answer, except that in small graphs it is more commonly false than true. To wit, I used the plantri program (by Brinkmann, Van den Camp 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:

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

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 Graphs 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.

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 than true. 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:

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

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 Graphs 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.

To the second part ("under what conditions is this true") I have no good answer, except that in small graphs it is more commonly false than true. 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:

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