"Euler's formula ( v−e+f=2 ) holds for all connected planar graphs. What if a graph is not connected? Suppose a planar graph has k components. What is the value of v−e+f now? "
I found online this question and I am going to give it a try . (Let me know if you agree)
- Every connected component is a planar graph itself , hence the Euler's formula holds true.
So we write down the formula for every single component:
$ v_i + f_i = e_i + 2$ . - Now we need to pay attention to what $f_i$ stands for: the number of faces inside each component $+1$ (the external face) . So $f_i = f_i' + 1$ where as $f_i'$ we note the number of faces inside the component.
- $\sum_{i=1}^{k}(v_i + f_i)=\sum_{i=1}^{k}(e_i+2) \rightarrow \sum_{i=1}^{k}(v_i + f_i)=\sum_{i=1}^{k}(v_i + f_i' +1)= v + \sum_{i=0}^{k}f_i' + k = e + 2k$.
- from the $k$ external faces we only need to count 1 , hence we write : $n +(\sum_{i=1}^{k}f_i'+1) + (k-1) = e + 2k \rightarrow v + f = 2k – (k-1) \rightarrow v + f = e + k + 1$
'''v + f = e + k + 1'''
Best Answer
Perfect! To be pedantic:
The sums at the beginning are $\sum_{i=1}^k$, not $\sum_{i=0}^k$, because you have $k$ connected components, not $k+1$.
The final answer is $k+1$, because the question is about the value of $v - e + f$.
Replace $n$ with $v$, and $n_i$ with $v_i$, to be coherent with the notations used in the original question.