Let $G$ be a simple plane graph where each face is either a triangle or a quadrilateral. Now, for each quadrilateral face $f$ of $G$, we insert a pair of crossing edges into $f$ to obtain $G'$. For example,
Then my question is:
- (a) If $G$ is 3-connected, is $G'$ simple （i.e., having no loops or multi-edges)?
In reverse,
- (b) if $G'$ is simple, must $G$ be 3-connected?
I know that if $G$ is triangulated (every face is a triangle), then the two questions above are self-evident.
But if $G$ contains at least one quadrilateral face, that is to say, if inserting a pair of crossing edges into at least one quadrilateral face is always possible, then I become somewhat ambiguous, unable to state it rigorously, and can only rely on intuition.
Here are some examples to validate my intuition. In the following figure, edge 'ab' has another copy in new graphs.
A pair of multi-edges in $G'$ may arise from either two newly added crossing edges (lying on two different quadrilateral faces) or from a newly added crossing edge and an existing edge in $G$.
In a word, I believe that $G'$ is simple if and only if $G$ is 3-connected.
Yes. Indeed, suppose that $G'$ is not simple. Then it has distinct edges $e$ and $e'$ between some distinct vertices $v$ and $u$. We claim that $G-\{v,u\}$ is disconnected. Indeed, otherwise when we draw the edges $e$ and $e'$, they will separate the plane into two regions, with all vertices of $G-\{v,u\}$ contained inside one of the regions. But then all inner faces of $G$ are inside of this region, so any of the edges $e$ and $e'$ either bounds the outer face of $G$ or is drawn inside it. By the construction of $G'$ at most one of the edges, say, $e$, can be drawn inside the outer face. But then the vertices $v$ and $u$ are adjacent by the edge $e'$ of the outer face, so the edge $e$ of $G'$ could not be drawn, a contradiction.
PS. Another proof should follow from the Steinitz's theorem, according to which the $3$-connected planar graphs are exactly the $1$-skeletons of convex polyhedra. Then each inserted edge should be contained in a unique face, so no multiedges should be introduced.
If order of $G$ is $3$ then $G$ is not $3$-connected. But if the order of $G$ is at least four then $G$ is $3$-connected. Indeed, let $v$ and $u$ be any two vertices of $G$. Let $G''$ be a graph constructed from $G$ similarly to $G'$ but with the condition that for each quadrilateral face of $G$ we insert only one edge $e$, and $e$ should be incident to both $v$ and $u$, if possible. Since $G'$ is simple, $G''$ is a triangulation (of order at least four). So $G''$ is $3$-connected. So for any distinct vertices $x$ and $y$ of $G-\{v,u\}$ there exists a path $P$ in $G''-\{v,u\}$ from $x$ to $y$. The path $P$ can be modified to a path in $G-\{v,u\}$ by replacing each its edge $ac$ of the quadrilateral face $abcd$ of $G$ by the pair $ab$, $bc$ or by the pair $ad$, $db$ of edges of $G$. This can always be done, because otherwise $\{b,d\}=\{v,u\}$, but then we had to insert the edge $bd$ instead of the edge $ac$, into the face $abcd$, a contradiction.
PPS. I expect that similarly we can prove the following claim.
Let $G$ be a simple plane graph with at least four vertices where each face is a polygon. (The conjectured possible equivalent conditions are: the boundary cycle of each face has no multivertices or the vertices of each face can be arranged into a cycle or $G$ is $2$-connected). Now, into each nontriangular face of $G$ we insert all its diagonals to obtain $G'$. Then $G$ is 3-connected iff $G'$ is simple.