Question

Do in Computing Mathematics or Discrete Mathematics

3. (8 pts) A graph is called planar if it can be drawn in the plane without any edges crossing. The Euler's formula states that v - etr = 2, where v, e, and r are the numbers of vertices, edges, and regions in a planar graph, respectively. For the following problems, let G be a planar simple graph with 8 vertices. (a) Find the maximum number of edges in G. (b) Find the maximum number of edges in G, if G has no circuits of length 3.

Answer 1

The solution of the given problem is below:

A simple planar graph with 8 vertices is given already.

The solution of (a) is:

The formula for maximum no of edges in a simple planar graph   is 3v-6.

where v denotes no of vertices.

so by formula we calculate max no of edgse when v=8 (Given)

max edges=3*8-6=18

So max no of edges possible with 8 vertex is 18.

The solution of (b) is:

If a simple planar graph has no cycle of length 3 then the maximum no of edgse is 2v-4 (It is a theorem).

so max no of edge =2*8-4=12.

Max no of edges in case when the graph has no cycle of length 3 will be 12.

Please upvote if u have still doubts comment me.