Question

To Determine a formula for \(r\) in terms of e, vand \(k\).

Short answer

The formula is \(r = e + k - v + 1\).

Step-by-step solution

 Given

A planar graph has \(k\) connected components, e edges, and v vertices. Plane is divided into \(r\) regions

The Concept of Euler's formula

It is written r + v = e + 2, where r is the number of faces, v the number of vertices, and e the number of edges.

Determine the formula

A planar graph has\(k\)connected components, e edges, and v vertices. Plane is divided into\(r\)regions.

We need to derive a formula for the number of regions\(r\)in terms of\(k\),\(v\)and\(e\).

Since\({\rm{G}}\)contains\({\rm{k}}\)connected components, we can make a graph connected by adding\(k - I\)edges to\({\rm{G}}\). We call the connected graph G'

Thus, we can use Euler's formula on the connected planar graph\({\rm{G}}\)', which has v vertices and\(e + k - 1\)edges.

\(r = (e + k - 1) - v + 2 = e + k - v + 1\)

\(r = e + k - v + 1\)