Q9Discrete Mathematics Structure
Question
2 marks
State the Kuratowski's theorem.
Answer
Kuratowski's theorem states a graph is planar iff it contains no subdivision of K5 or K3,3.
Kuratowski's Theorem provides a necessary and sufficient condition for a graph to be planar. It states: A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of the complete graph or the complete bipartite graph .