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)?

  • $\begingroup$ You need some additional assumptions, such that the graph is finite. Otherwise one can construct counterexamples. $\endgroup$ Dec 8 '17 at 18:37
  • $\begingroup$ Sorry, okay I am speaking about finite graphs! $\endgroup$
    – StefanH
    Dec 8 '17 at 18:38

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.

  • 1
    $\begingroup$ Sorry, thats not valid, as the proofs of Eulers formula use this fact (inductively removing edges until we arrive at a tree, and then using that a graph is a tree if its embedding just has one face)! I mentioned that at the end somehow. I am looking for a proof from first principles or without such "circularity"! $\endgroup$
    – StefanH
    Dec 8 '17 at 18:37
  • 1
    $\begingroup$ @StefanH: You can continue the induction by removing a vertex of degree 1 and its coincident edge, which (but that must be proved, of course) leaves the number of faces unchanged. Then you can get all the way down to a graph consisting of one vertex, no edges, and (easily) one face. $\endgroup$ Dec 8 '17 at 18:42
  • $\begingroup$ @HenningMakholm Yes, that reasoning should work! (and in the unproven part you mentioned just us the topology of $\mathbb R^2$ and connecting paths) $\endgroup$
    – StefanH
    Dec 8 '17 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.