Solution

The correct answer is A and B only.

Key Points

• A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
• Planar graphs follow Kuratowski's theorem, which states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K₅ (complete graph on five vertices) or K_3,3 (complete bipartite graph on six vertices).
• To determine if a graph is planar, one can try to draw it in such a way that no edges cross each other, except at the vertices.

Additional Information

• Graphs A and B are determined to be planar by verifying that they can be drawn without any edge crossings.
• Graph C is not planar because it contains a subgraph that is homeomorphic to K₅ or K_3,3, which means it cannot be drawn without edge crossings.
• Planar graphs are useful in various fields such as computer networking, geography, and circuit design, where planar embeddings help to minimize complexity and avoid intersections.
• Graph theory provides various algorithms to check for planarity, such as the Hopcroft and Tarjan planarity testing algorithm.