BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Thursday , August 17 2017
Home / Discrete mathematics / Euler’s formula for planner graphs| Discrete Mathematics

Euler’s formula for planner graphs| Discrete Mathematics

Proof: We have to proved V-E+R=2 for any connected planner graph.

Where v, e, r are the number of vertices, edges and regions of the graph respectively.

The proof proceeds by induction on the number of edges. As the basis of induction we observe that for the two graphs with a single edge shown in fig-1     v-e+r=2 is satisfies.

eu2

As the induction step, we assume that V-E+R=2 is satisfied in all graphs with n-1 edges.

Let G be a connected graph with n edges. If G has a vertex of degree 1, the removal of this vertex together with the edge incident with it will yield a connected graph G′ as illustrated in fig-2. Since V-E+R=2 is satisfied G′, it is also satisfied in G.

eu3

Because putting the removed edge and vertex back into G will increase the count of edges by 1 but will not change the count of regions. If G has no vertex of degree 1, the removal of any edge in the boundary of finite region will yield a connected graph G′ as shown in fig-3. Since V-E+R=2 is satisfied G′, it is also satisfied in G.

eu4

 

Fig-3

Because putting the removed edge back into G′ will increase the count of edges by 1and the regions by 1, but will not change the count of vertices.

Hence V-E+R=2.

This is the required Euler’s formula for planner graphs.

 

Check Also

Procedure for computing shortest distance| Discrete Mathematics

Solution: The procedure for computing the shortest distance/path from a to any vertex G. Initially, ...

Leave a Reply

Your email address will not be published. Required fields are marked *