Show that no matter in what way we embed a planar graph, we always get the same number of faces.

This is trivial for connected graphs, because Euler's formula applies and shows that $f = 2 - n + e$, and no matter how we embed the graph, the number of vertices and edges is already fixed.

I think that for disconnected graphs the formula helps as well: say we have $m$ components. Then we add one edge for each component so $m-1$ edges to connect them. The formula now applies, and we have added $m-1$ edges so $f = 2 - n + e + m-1$. The outer face is the same because we do not create new faces, so when we remove the added edges we get $f$. Maybe I am being too obnoxious about this - is there an easier way? Also is my idea correct?

  • 1
    $\begingroup$ Looks good to me, and I don't think you're being obnoxious at all. $\endgroup$ – saulspatz Apr 4 '18 at 19:36
  • $\begingroup$ Thank you very much @saulspatz $\endgroup$ – mandella Apr 4 '18 at 19:37
  • 1
    $\begingroup$ That's the correct way to extend Euler's formula for disconnected graphs. The fact about the faces is a consequence. $\endgroup$ – Ethan Bolker Apr 4 '18 at 19:37
  • $\begingroup$ @EthanBolker Oh, good point! Thank you. $\endgroup$ – mandella Apr 4 '18 at 19:38
  • 1
    $\begingroup$ Your idea is good. The problem is a little bit murky for disconnected graphs, since then the "faces" aren't all simply connected (e.g., embed two triangular graphs with one enclosing the other). If you take "face" to mean a connected component of the complement of the embedded graph, then your argument is fine. $\endgroup$ – Rob Arthan Apr 4 '18 at 20:08

Your Answer

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

Browse other questions tagged or ask your own question.