Which of the following Graph is(are) planar?

Answer: The first and the second graphs are planar; the third graph is non-planar.

Key idea: Use Kuratowski's theorem: a graph is non-planar if and only if it contains a subdivision of K5 or K3,3. You can also attempt to produce a crossing-free embedding as a constructive check.

• First graph: This graph can be drawn without any edge crossings. It does not contain a subdivision of K5 or K3,3, so it is planar. One convenient embedding is to place the three outer vertices at the corners of a triangle and route any interior edges inside that triangle without crossings.

• Second graph: This graph also admits a planar embedding. For example, place some vertices on a circle and draw the remaining edges as non-crossing chords, or place one vertex in the center and draw spokes to boundary vertices. No K5 or K3,3 subdivision appears, so it is planar.

• Third graph: This graph contains a subdivision of a non-planar complete graph (for example K5) or a subdivision of K3,3. By Kuratowski's theorem, the presence of such a subdivision makes the graph non-planar, so it cannot be embedded in the plane without edge crossings.

Conclusion: Therefore the planar graphs are the first and the second; the third graph is non-planar.

Tip: When unsure, look for K5 or K3,3 subdivisions or try to construct a drawing with no crossings. Euler's formula (V - E + F = 2 for connected planar graphs) can also provide quick contradictions for dense graphs.