StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q16SE

Expert-verifiedFound in: Page 738

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\).

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

**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.**

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.

94% of StudySmarter users get better grades.

Sign up for free