My few doubts about the fact that the minimal cut set of the maximal plane graph induces to a cycle.

Question

I read the paper [Baybars, Ilker. "On k-path hamiltonian maximal planar graphs." Discrete Mathematics 40.1 (1982): 119-121.] and noticed following lemma like this

Lemma. Let $G=(V,E)$ be a maximal planar graph and let $S \subset V$ be a minimal separating set (i.e. $G-S$ is disconnected. Then $S$ induces a cycle in $G$.

However, the author did not prove this theorem. So I went to find an original manuscript [see here ] that seemed to be the same author. Here it provided a relatively detailed proof, but I still have some doubts about this proof.

Let $\kappa(G)$ denote the connectivity number of the graph. Lemma 4 refers to the following:

Lemma 4 If G is maximal planar, then $3 \le \kappa(G) \le 5$.

My doubts are listed below:

1. This article does not mention the meaning of minimal separating set . According to the standard definition, should be defined like this:

A minimal seperating set $S$ is seperating set such that no proper subset of $S$ is a seperating set.

The minimum seperating set is seperating set with the minimum number of elements.

Note that minimal seperating set is not minimum seperating set in some cases. As shown in the figure below. Vertex set $\{ 4,5,6,7,8,9 \}$ is minimal seperating set but not minimum seperating set.

Therefore, we can't seem to get $|S| \le 5$.

2. I noticed this sentence in the proof.

Clearly, exactly two vertices in $S$ must lie in the exterior face of $G$.

I'm not sure why.

3. $S$ induces a cycle in $G$. Is there a chord on the cycle $G[S]$?

A cycle has a chord if there are a pair of vertices that are adjacent, but not along the cycle.

Based on the above questions, it is not clear whether this lemma is really correct. So ask for help. Thank you in advance!

Answer 1

1. As you mentioned in comments, it doesn't seem to matter whether minimal or minimum separating sets are meant; although a non-shrinkable separating set may have more than 5 vertices, that doesn't seem to play a further role.
2. This statement "exactly two vertices in $S$ must lie in the exterior face of $G$" isn't actually true, as seen in the example graph in your question. Examples which are actually a minimum separating set (size three, for example) can be come up with as well.

What the author seems to mean is something like "Assuming to the contrary that $S$ does not induce a cycle in $G$, then exactly two vertices in $S$ must lie on the exterior face of $G$."

Suppose $G_1$ and $G_2$ are the connected components left after removing $S$. If there is no path from the exterior face to any point in S, then there must be edges between $G_1$ and $G_2$. This is true, but it seems kind of tricky to establish (and it's definitely not "clear" as the author claims.)

3. No, there does not have to be a chord on $G[S]$. Consider this graph of a triangular bipyramid, with separating set $\{a,b,c\}$: