1 Determine whether each graph is planar If it is planar fin

1. Determine whether each graph is planar. If it is planar, find a planar embedding. If not, explain why not. 2. Let G be a connected plane graph with V 23 vertices and F faces. Show that F s 2V - 4. 3. Find the chromatic number of each graph. Justify your answer

Solution

1.

graphs which can be completed without their edges crossing and some graphs which cannot. If a graph

can be drawn in the plane (on a sheet of paper) without any of its edges crossing, it is said to be

planar.

a> is not a planar graph as the edges are crossing each other.

b> is not a planar graph as the edges are erossing each other.

c> is not a planar graph as the edges are erossing each other.

.