• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q16SE

Expert-verified Found in: Page 738 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # To show the expression $$e \le 2v - 4{\rm{ if }}v \ge 3$$.

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

See the step by step solution

## Step 1:  Given

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

## Step 2: 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.

## Step 3: 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. ### Want to see more solutions like these? 