Kuratowski's theorem A graph G is planar if and only if G does not contain K5,K3.3,or a subdivision of K5 or K3.3 as a subgraph. -A graph G'is called a subdivision of a graph G if one or more vertices of degree 2 are inserted into one or more edges of G.Kuratowski’s theorem • A graph G is planar if and only if G does not contain K5 , K3,3 , or a subdivision of K5 or K3,3 as a subgraph. – A graph G’ is called a subdivision of a graph G if one or more vertices of degree 2 are inserted into one or more edges of G