H29 Let G be a connected planar graph with three or more ver

H29 Let G be a connected planar graph with three or more vertices, and let v, e, and r be as usual. (a) Use the regional degrees in any plane diagram of G to show that r is less than or equal to 2e/3. (b) Prove that e is less than or equal to 3v-6.

Solution

We know that Euler\'s formula says that v-e+f=2

and by hand shaking theorem says that \"Sum of the vertex degrees is 2e\"

by Second hand shaking theorem says for planar graphs that \"Sum of the face degrees is 2e\"

According to our problem given that connected planar graph with three or more vertices

let v be the vertices e be edges and r be the faces

then by the above known theorems

the sum of the degrees of the region is equal to twice the number of edges

but each region must have degree >=3

so we have 2e>=3r

              then r<=2e/3

Euler\'s formula says v-e+f=2 here instead of f in our problem given r

                           so r=e-v+2

           combining this with r<=2e/3

                              e-v+2<=2e/3

                               so (e/3)-v+2>=0

                                     (e/3)<=v-2

                                      e<=3v-6

which gives the proof