3

Let $G=(V,E)$ be a planar graph. Suppose a planar representation of $G$ has been chosen and that $$v-e+f=2,$$ where $v,e$ and $f$ are the number of vertices, edges and faces respectively. See Wikipedia.

Does this imply that $G$ must be connected?

jake
  • 31
  • 1
    Yes. There's a more general form of the formula, with a term for the number of components. Exercise: work it out (or look it up). – Gerry Myerson Oct 13 '13 at 12:30
  • I don't see how this question is a converse for the formula. I feel that a converse would be something like, if it doesn't satisfy the equation you wrote, then it isn't planar. But that would be weird because how would you count "faces" of a non-planar diagram? I'm actually pretty interested in that and might post a separate question! – j0equ1nn Oct 18 '18 at 17:29

1 Answers1

2

Suppose that the graph is not connected but still is planar. Then there are two graphs that are disconnected such that $v_1-e_1+f_1=2$ and $v_2-e_2+f_2=2$. On the other hand we have $v_1+v_2=v$ and $e_1+e_2=e$ but $f_1+f_2=f+1$. So we get: $$ v_1-e_1+f_1+ v_2-e_2+f_2=4\implies v-e+f=3 $$ which means that the original graph will not be planar and therefore we arrived at a contradiction. So the graph should be connected.

Arash
  • 11,131
  • thank you for your help. I do have one question. How do you get $f_1+f_2=f+1$. I've checked it, but I get $f_1+f_2=f+2$. – jake Oct 13 '13 at 14:33
  • each face of each subgraph is also a face of original graph. There is only one common face between two disconnected subgraph. So by adding the number of faces of these two subgraphs, we count one face twice. – Arash Oct 13 '13 at 15:05
  • @jake: In Arash's answer, given a graph that has two connected components, the outer region of the first and second component are the same and in order to not count the outer face twice, we need to subtract 1, i.e. $f$ should equal $f_1+f_2-1$. – AG. Oct 14 '13 at 06:41