A planar 2-connected graph. G-e1-e2 is not connected. Do e1 and e2 belong to the same face?

115 Views Asked by At

Problem:

$G$ is a planar 2-connected graph. $G-e_1-e_2$ is not connected.

Is it true, that $e_1$ and $e_2$ belong to the same face?

Solution:

I thought about the fact:

$G$ is a planar 2-connected graph $\iff$ its every face is a simple cycle (1).

So, let $e_1$ and $e_2$ belong to the different faces. Using the fact (1) we can say that $e_1$ and $e_2$ belong to the different simple cycles, but if we delete 2 edges from two different simple cycles of 2-connected graph, it will be connected $=>?!$ Сontradiction, $e_1$ and $e_2$ belong to the different faces.

Is this solution correct?

1

There are 1 best solutions below

0
On BEST ANSWER

Your proof doesn't work because both the statements "$e_1$ and $e_2$ belong to different faces" and "$e_1$ and $e_2$ belong to different simple cycles" are imprecise, and once you make them precise, the second no longer follows from the first.

We are assuming for contradiction that it is not true that $e_1$ and $e_2$ belong to the same face. Well, actually, $e_1$ and $e_2$ might each belong to up to two faces. So the negation that we're assuming for contradiction should read "there is no face $F$ which contains both $e_1$ and $e_2$".

All faces are simple cycles, but not all simple cycles are faces. So we cannot conclude the broader statement "there is no simple cycle $C$ which contains both $e_1$ and $e_2$". There might be some cycles like this: they're just not faces.

The statement "If $G$ is a $2$-connected graph and $e_1$ and $e_2$ are edges such that no simple cycle $C$ contains both $e_1$ and $e_2$, then $G-e_1-e_2$ is connected" is true, though it requires proof. Even so, it does not solve this problem, because we're not given enough information to prove the hypothesis of this statement.


To prove this result, suppose that $G-e_1-e_2$ is disconnected. Then, in a plane embedding of $G$, we can draw a closed curve around one of the two components of $G-e_1-e_2$ which doesn't touch any vertices or edges of $G$.

Both $e_1$ and $e_2$ must go from that component to the other component of $G-e_1-e_2$, so they must both cross that curve. This means that some segment of that curve is a path which goes from the interior of $e_1$ to the interior of $e_2$, without touching any other edges or any vertices. This is only possible if $e_1$ and $e_2$ are part of the same face.