Theorem 5.30: Kuratowski's Theorem (1930) a graph is planar if and only if it contains no subgraph that is homeomorphic of Ks or K3.3 (1)If G is a planar graph, then it contains no subgraph that is homeomorphic of K 5, and it contains no subgraph that is homeomorphic of K3.3 (2)If a graph g does contains no subgraph that is homeomorphic of ks and it contains no subgraph that is homeomorphic of K33 then g is a planar graph (3)If a graph g contains a subgraphs that is homeomorphic of Ks, then it is a nonplanar graph If a graph g contains a subgraph that is homeomorphic of K3.3, then it is a nonplanar graph. (4)If G is a nonplanar graph, then it contains a subgraph that is homeomorphic of Ks or K3.3▪ Theorem 5.30: Kuratowski’s Theorem (1930). A graph is planar if and only if it contains no subgraph that is homeomorphic of K5 or K3,3. ▪ (1)If G is a planar graph, then it contains no subgraph that is homeomorphic of K5 , and it contains no subgraph that is homeomorphic of K3,3 ▪ (2)If a graph G does contains no subgraph that is homeomorphic of K5 and it contains no subgraph that is homeomorphic of K33 then G is a planar graph ▪ (3)If a graph G contains a subgraphs that is homeomorphic of K5 , then it is a nonplanar graph. If a graph G contains a subgraph that is homeomorphic of K3,3, then it is a nonplanar graph. ▪ (4)If G is a nonplanar graph, then it contains a subgraph that is homeomorphic of K5 or K3,3