edited by
715 views

1 Answer

1 votes
1 votes

The result to be utilised here is that K3,3(complete bipartite graph with 3 vertices in each partition) and k5(5 vertex complete graph) are simplest non-planer graphs.

KURATOWSKI THEOREM: ANY GRAPH WHICH CONTAINS SUBGRAPHS HOMEOMORPHIC TO K3,3 OR K5 ARE NON-PLANER (NOTE THAT IT IS AN IF AND ONLY IF CONDITION).

A graph is non-planar iff we can turn it into K3,3 or K5 by:

  1. Removing edges and vertices. (Making a subgraph.)

  2. Collapsing degree-two vertices into a single edge.

  3. Applying an isomorphism to turn it into K3,3 or K5.

In the above graph , 

  1. remove vertex e
  2. put {a,d,g} in one partition
  3. put {b,c,f} in other partition
  4. remove edges between {a,d},{a,g},{g,d},{b,c},{b,f},{f,c}

REMAINING GRAPH

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
swati96 asked Jun 18, 2018
1,188 views
How many non-isomorphic simple graphs are there with five vertices and three edges?
0 votes
0 votes
1 answer
4
Mk Utkarsh asked Mar 1, 2018
2,449 views
How much storage is needed to represent a simple graph with n vertices and m edges using.a) adjacency lists?b) an adjacency matrix?c) an incidence matrix?