1
$\begingroup$

I am trying to figure out how to extend Euler's formula, n - e + f = 2, to contain a connected component denoted k. I am new to graph theory so I am not sure if the way I got there is correct or if there is a better way to show it.

I started by converting a regular graph into a connected one. I inserted e = e + k - 1 so that each new edge would connect two components in a graph and I got n - e + f = k + 1 which I know is the right answer. Is there a better/easier way to show how Euler's formula can contain a connected component?

Thanks in advance.

$\endgroup$
2
  • $\begingroup$ That seems like a very simple proof - I don't know that you could ask for much simpler. I gave another possible proof here: math.stackexchange.com/questions/720649 $\endgroup$ – Perry Elliott-Iverson Mar 31 '14 at 17:36
  • $\begingroup$ I understand that is is simple. This is fundamental material and I want to make sure I completely understand it so it doesn't come back to haunt me later. Thanks for the response and the link; it makes more sense now. $\endgroup$ – datprog Mar 31 '14 at 18:10
1
$\begingroup$

Assume (without loss of generality) that all connected components share the same "outer face". If we don't count the outer face, $n_i-e_i+f_i=1$ for each connected component. So when we sum the values for each of the $k$ connected components, plus the outer face, we get $n-e+f=k+1$.

$\endgroup$

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.