a question involving Eular's formula
G is a planar graph that has n vertices, e edges, r regions, and
k connected components.
Show that the Euler's Formula for G can be written as: n - e + r = k + 1.
(Remember if G is connected, then k = 1, which means Euler's Formula will be degenerated to n - e + r = 2.)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~
I am a super-newbie to discrete math, and I don't even know where I should start with this question
I only know that the Eular's theorem for any connected planar graph is n - e + r = 2.
But I don't know how could I transform that formula to n - e + r = k + 1.
any hints or helps will be appreciated, thanks for reading this post
Re: a question involving Eular's formula
Do you need to derive the Euler's formula for planar graphs with any number of components from the Euler's formula for graphs with one component? This is easy to do by induction on the number of components. If that number is k + 1 for k > 0, break the graph into two subgraphs, with k components and 1 component. Express the number of vertices, edges and regions in the whole graph through the corresponding numbers for the two subgraphs.