Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 10: Q18RE (page 738)

a) What is Euler’s formula for connected planar graphs?

b) How can Euler’s formula for planar graphs be used to show that a simple graph is nonplanar?

Short Answer

Expert verified

  • (a) r = e - v + 2 is Euler’s formula for connected planar graphs

  • (b) If the degree of the vertex of a graph is at least 5, then it is not a planar graph by using Euler’s formula

Step by step solution

01

Solution of Euler’s formula for connected planar graphs

  • Let G be a connected planar graph with the number of edges and vertices as e and v, respectively.

  • Let r be the number of regions in a planar representation of a graph.

  • Then, the relation between the regions and the number of vertices and edges are represented by the formula, r = e - v + 2

02

Use of Euler’s formula for planar graphs

  • The planar graph should satisfy the formula r = e - v + 2.

  • Assume that the graph is planar and evaluate the number of regions formed using the formula r = e - v + 2.

  • Then, try to form a planar graph using the obtained number of regions.

  • If the graph can be made without crossing the edges, then it is planar, otherwise it is non planar.

  • If the degree of the vertex of a graph is at least 5, then it is not a planar graph.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Which graphs have a chromatic number of 1?

Find the shortest path between the vertices\({\bf{a}}\)and\({\bf{z}}\)that passes through the vertex f in the weighted graph in Exercise 3 in Section 10.6.

Suppose that to generate a random simple graph with n vertices we first choose a real number p with\({\bf{0}} \le {\bf{p}} \le {\bf{1}}\). For each of the\({\bf{C}}\left( {{\bf{n,2}}} \right)\)pairs of distinct vertices we generate a random number x between 0 and 1.

If\({\bf{0}} \le {\bf{x}} \le {\bf{p}}\), we connect these two vertices with an edge; otherwise these vertices are not connected.```

a) What is the probability that a graph with m edges where\({\bf{0}} \le {\bf{m}} \le {\bf{C}}\left( {{\bf{n,2}}} \right)\)is generated?

b) What is the expected number of edges in a randomly generated graph with n vertices if each edge is included with probability p?

c) Show that if\({\bf{p = }}\frac{{\bf{1}}}{{\bf{2}}}\)then every simple graph with n vertices is equally likely to be generated.

A property retained whenever additional edges are added to a simple graph (without adding vertices) is called monotone increasing, and a property that is retained whenever edges are removed from a simple graph (without removing vertices) is called monotone decreasing.

Suppose that a connected graph \(G\) has \(n\) vertices and vertex connectivity \(\kappa \left( G \right) = k\). Show that \(G\) must have at least \(\left\lceil {\frac{{kn}}{2}} \right\rceil \) edges.

a) Show that if the diameter of the simple graph\({\bf{G}}\)is at least four, then the diameter of its complement\({\bf{\bar G}}\)is no more than two.

b) Show that if the diameter of the simple graph\({\bf{G}}\)is at least three, then the diameter of its complement\({\bf{\bar G}}\)is no more than three.
See all solutions

Recommended explanations on Math Textbooks

Applied Mathematics

Read Explanation

Pure Maths

Read Explanation

Mechanics Maths

Read Explanation

Calculus

Read Explanation

Discrete Mathematics

Read Explanation

Logic and Functions

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free