**Planar Graphs-**

A planar graph is a graph that can be drawn in a plane such that none of its edges cross each other.

**Example-01:**

This graph is an example of a planar graph.

**Example-02:**

Both the above graphs are equivalent and examples of planar graphs.

- At first sight, first version of the graph may not seem to be planar because it has edges crossing each other.
- But we can redraw the first version as shown in the second version which consists of no two edges crossing each other and therefore, both the graphs are planar.

**Chromatic Number of Planar Graphs-**

Chromatic number of planar graphs = Less than or equal to 4 |

Thus, any planar graph will require maximum 4 colors for coloring its vertices such that no two adjacent vertices have same colors.

**Regions of the plane-**

- The planar representation of the graph splits the plane into connected areas called as regions of the plane.

**Degree of the Regions-**

Each region has some degree associated with it given as-

- Degree of an interior region = Number of edges enclosing that region
- Degree of an exterior region = Number of edges exposed to that region

In a simple planar graph, degree of each region is at least 3 (>=3) |

**Example-**

The following planar graph splits the plane into 4 regions-

In this graph-

- Degree (R1) = 3
- Degree (R2) = 3
- Degree (R3) = 3
- Degree (R4) = 5

**Properties of Planar Graphs-**

**Property-01:**

In any planar graph,

Sum of degrees of all the vertices = 2 x Total number of edges in the graph

**Property-02:**

In any planar graph,

Sum of degrees of all the regions = 2 x Total number of edges in the graph

**Special Cases- **

**Case-01:**

In any planar graph, if degree of each region is K, then-

K x |R| = 2 x |E| |

**Case-02:**

In any planar graph, if degree of each region is at least K (>=K), then-

K x |R| <= 2 x |E| |

**Case-03:**

In any planar graph, if degree of each region is at most K (<=K), then-

K x |R| >= 2 x |E| |

**Property-03: Euler’s Formula**

If G is a connected planar simple graph with ‘e’ edges, ‘v’ vertices and ‘r’ number of regions in the planar representation of G, then-

r = e – v + 2 |

The formula remains same in all the planar representations of the graph.

**Property-04:**

If G is a planar graph with k components, then-

r = e – v + (k + 1) |

**PRACTICE PROBLEMS BASED ON PLANAR GRAPHS-**

**Problem-01:**

Let G be a connected planar simple graph with 25 vertices and 60 edges. Find the number of regions in G.

**Solution-**

By Euler’s formula, we know-

r = e – v + 2

We have, v = 25 and e = 60. Substituting the values, we get-

r = 60 – 25 + 2

∴ r = 37

Thus, Total number of regions in G = 37

**Problem-02:**

Let G be a planar graph with 10 vertices, 3 components and 9 edges. Find the number of regions in G.

**Solution-**

By Euler’s formula, we know-

r = e – v + (k+1)

We have, v = 10, e = 9 and k = 3. Substituting the values, we get-

r = 9 – 10 + (3+1)

∴ r = 3

Thus, Total number of regions in G = 3

**Problem-03:**

Let G be a connected planar simple graph with 20 vertices and degree of each vertex is 3. Find the number of regions in G.

**Solution-**

**Step-01: Calculation of total number of edges in G-**

By sum of degrees of vertices theorem, we know-

Sum of degrees of all the vertices = 2 x Total number of edges

We have, v = 20 and degree of each vertex = 3. Substituting the values, we get-

20 x 3 = 2 x |E|

∴ |E| = 30

Thus, Total number of edges in G = 30

**Step-02: Calculation of total number of regions in G-**

Now, By Euler’s formula, we know-

r = e – v + 2

We have, v = 20 and e = 30. Substituting the values, we get-

r = 30 – 20 + 2

∴ r = 12

Thus, Total number of regions in G = 12

**Problem-04:**

Let G be a connected planar simple graph with 35 regions, degree of each region is 6. Find the number of vertices in G.

**Solution-**

**Step-01: Calculation of total number of edges in G-**

By sum of degrees of regions theorem, we know-

Sum of degrees of all the regions = 2 x Total number of edges

We have, r = 35 and degree of each region = 6. Substituting the values, we get-

35 x 6 = 2 x |E|

∴ |E| = 105

Thus, Total number of edges in G = 105

**Step-02: Calculation of total number of vertices in G-**

Now, By Euler’s formula, we know-

r = e – v + 2

We have, r = 35 and e = 105. Substituting the values, we get-

35 = 105 – v + 2

∴ v = 72

Thus, Total number of vertices in G = 72

**Problem-05:**

Let G be a connected planar graph with 12 vertices, 30 edges and degree of each region is K. Find the value of K.

**Solution-**

**Step-01: Calculation of total number of regions in G-**

By Euler’s formula, we know-

r = e – v + 2

We have, v = 12 and e = 30. Substituting the values, we get-

r = 30 – 12 + 2

∴ r = 20

**Step-02: Calculation of value of k-**

Now, By sum of degrees of regions theorem, we know-

Sum of degrees of all the regions = 2 x Total number of edges

So, we have-

20 x k = 2 x 30

∴ k = 3

Thus, Degree of each region in G = 3

**Problem-06:**

What is the maximum number of regions possible in a simple planar graph with 10 edges?

**Solution-**

We know, In a simple planar graph, degree of each region is >= 3

So, we have-

3 x |R| <= 2 x |E|

We have, |E| = 10. Substituting the value, we get-

3 x |R| <= 2 x 10

|R| <= 6.67

|R| <= 6

Thus, Maximum number of regions in G = 6

**Problem-07:**

What is the minimum number of edges necessary in a simple planar graph with 15 regions?

**Solution-**

We know, In a simple planar graph, degree of each region is >= 3

So, we have-

3 x |R| <= 2 x |E|

We have, |R| = 15. Substituting the value, we get-

3 x 15 <= 2 x |E|

|E| >= 22.5

|E| >= 23

Thus, Minimum number of edges required in G = 23

Get more notes and other study material of **Graph Theory.**

Watch video lectures by visiting our YouTube channel **LearnVidFun**.