Chapter 13, Problem 1RE

1. Show that the graph below is planar by drawing an isomorphic plane graph with straight edges.

   

2. Label the regions defined by your plane graph and list edges that form the boundary of each region.

3. Verify that $V-E+R=2,N\le 3V-6$. (Recall the boundaries of all regions)

To determine

To prove: the graph below is planar by drawing an isomorphic plane graph with straight edges.

Explanation of Solution

Given information:

Prove:

Graph A

If we redraw the graph as follows

Graph B

Now, you should notice that for graph A and B.

1. Number of vertices are equal

2. Number of edges are equal

3. Degree sequence are equal

To determine

Labeled regions which is defined by your plane graph and list edges that form the boundary of each region.

Explanation of Solution

Given information:

Explanation:

I label and numbering the surface by drawing a circle around a number

To determine

To prove: $V-E+R=2,N\le 3V-6$

Explanation of Solution

Given information:

Prove:

Here,

$\begin{array}{l}V=7,E=13,R=8\\ \therefore V-E+R=7-13+8\\ =2\end{array}$

And,

$\begin{array}{l}N=22\\ \therefore N=22\le 26=2E\end{array}$