Proving rigorously that a planar graph with at least two faces contains a cycle

363 Views Asked by At

A finite graph $G = (V, E)$ is called planar if there exists an embedding $\varphi : V \to \mathbb R^2$ such that $$ \{ u, v \} \in E \Leftrightarrow \mbox{there exists a unique Jordan curve between $\varphi(u)$ and $\varphi(v)$} $$ and two such Jordan curves could just coincide at their endpoints, let's denote by $\varphi(\{u,v\})$ the point set of this curve. Now a face is a maximal connected open subset of $\mathbb R^2$ minus the points which belong to this embedding (i.e. to points and curves). All graphs are assumed to be finite!

So according to the Jordan Curve Theorem if there exists some cycle we have at least two faces, and more specifically every cycle that does not contain any other cycle uniquely determines some (interior) face.

But I nowhere see a way to prove that If I have at least two faces, then my graph must contain a cycle (this is somehow the reverse of what Jordans Theorem gives).

Similarly, I do not see that the following (mentioned in these ntoes) follows from Jordan:

  • every cut-edge belong belongs to only one face (or if it belongs to two faces, it could not be a cut-edge, which in some sense resembles the reasoning that if I have two faces, there must be some cycle involved)

  • a plane graph is acyclic iff it just has one face (again, more than one face should imply it is cyclic)

So, I do not see that this follows from Jordan Theorem. But then how to prove these somehow often used and important facts (for example in the base case of an inductive proof of Eulers formula)?

1

There are 1 best solutions below

3
On BEST ANSWER

We have Euler formula for planar graph $$V-E+F=2$$ and if $E\geq 2$ we have $E\geq V$. Now if this graph doesn't have cyclic it is a forest, so we have $$E=V-1<V$$ A contradiction.