Question

To show the expression \(e \le 2v - 4{\rm{ if }}v \ge 3\).

Short answer

The expression is shown \(e \le 2v - 4{\rm{ if }}v \ge 3\).

Step-by-step solution

 Given

A connected bipartite planar simple graph has e edges and v vertices.\(v \ge 3\)

The Concept ofbipartite graph

Abipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and, that is every edge connects a vertex in to onein.

Determine the expression

Let the vertices of\({\rm{G}}\)be partitioned into two sets\({V_1}\)and\({V_2}\)

A bipartite graph can only have circuits of even length, because if we have a vertex in\({V_1}\), then we need to use an even number of edges to end up at a vertex in\({V_1}\)again.

Then a bipartite graph does not have a circuit of length 3 and we know that \(e \le 2v - 4\) by corollary.