How high the connectivity of a planar graph can ensure that any two faces share at most two vertices?

63 Views Asked by At

Once I asked the following question.

Question 1 (solved): Do any two faces share with at most one edge in a 3-connected plane graph?

As anilch reminded, the dual graph of a 3-vertex-connected (or,3-edge -connected) planar graph is simple. So the question is solved.

The following broader question might be interesting.

Question 2: Do any two faces share with at most two vertices in a 3-vertex-connected plane graph?

If ''3" is not guaranteed, what if we choose "4" or "5"? Disprove it or prove it.

I'm looking for some counterexamples, but so far I haven't found any.


Without finding a counterexample, I thought the following claim would be true:

Claim: Let $G$ be a $3$-vertex-connected graph. Then any two faces $f_1$ and $f_2$ have at most two vertices in common. Further if $f_1$ and $f_2$ share two vertices $v_1,v_2$, then the edge $v_1v_2$ is the unique edge shared by $f_1$ and $f_2$.

A Outline of proof: If there are two faces $f_1$ and $f_2$ such that they have three or more vertices in common. By properly choosing two shared vertices $x,y$, we can construct a closed curve that is crosses through these two vertices and falls in $f_1$ and $f_2$. By the closed curve, we can see clearly that $x, y$ is a 2-cut set, a contradiction.

![enter image description here