Does a triangulation $T$ such that $\kappa(T)=3$, $\kappa'(T)=4$ and $\delta(T)=5$ exist?

Question

Some terminology and notation:

• A simple plane graph in which all faces are triangular faces is called a triangulation.
• The vertex connectivity of a graph $G$, written as $\kappa(G)$, is the smallest number of vertices whose deletion from $G$ disconnects $G$.
• The edge connectivity of a graph $G$, written as $\kappa'(G)$, is the smallest number of edges whose deletion from $G$ disconnects $G$.
• The minimum vertex degree of a graph $G$, written as $\delta(G)$, is the smallest vertex degree of $G$.

By the well-known Whitney inequality, for any graph $G$, we have

$$\kappa(G)\le \kappa'(G)\le \delta(G).$$

Now I'd like to find a triangulation $T$ such that $\kappa(T)< \kappa'(T)< \delta(T).$

We know that for any plane graph with minimum degree $\le 5$ and any triangulation with the number of vertices $\ge 4$ has vertex connectivity at least $3$. The above question can be equivalent to:

Qustion: Find a triangulation $T$ such that $\kappa(T)=3$, $\kappa'(T)=4$ and $\delta(T)=5.$

I haven not found an example where the number of vertices is 24 or less by a computer program (plantri and Mathematica). Is there no such example in all triangulations?

geng = StartProcess[{"D:/plantri52/plantri", "24", "-m5c3x", 
   "-g"}];
While[(line = ReadLine[geng]) =!= EndOfFile,
 lineg = ImportString[line, "Graph6"];
 If [EdgeConnectivity[lineg ] == 4, 
 Print[lineg] && Break[]]]

Answer 1

A triangulation with minimum degree $5$ cannot have edge connectivity $4$.

Suppose we delete $4$ edges form a triangulation $G$ to leave two components $G_1, G_2$. Let $F$ be the face of the resulting graph that has a boundary both in $G_1$ and in $G_2$.

Suppose we can choose vertices $v_1, v_2, v_3$ in $G_1$ and vertices $w_1, w_2, w_3$ in $G_2$ that lie on $F$. Then we can draw the five edges $\{v_1 w_1, v_1 w_2, v_2 w_2, v_2 w_3, v_3 w_3\}$ without crossing, getting a planar graph with the same number of vertices as the original $G$, but more edges. This is a contradiction.

So one of $G_1$ or $G_2$ only has two or fewer vertices on $F$. This is only possible if that component only has two or fewer vertices total. But that contradicts our minimum degree condition:

• A single vertex would have $5$ edges to the other component, not $4$.
• Two vertices might share an edge, but then they'd have $8$ edges to the other component, not $4$.