G1 and G2 are two graphs as shown below. Which one of the following statements…

CONCEPT

A graph is planar when it can be drawn in the plane so that edges meet only at shared endpoints. Kuratowski’s theorem turns that into a checkable structural property: a graph is non-planar if and only if it has a subgraph homeomorphic to K5 or to K3,3. Crossings in one particular drawing therefore prove nothing on their own — non-planarity is proved by exhibiting a Kuratowski subgraph, and planarity is proved by exhibiting one crossing-free redrawing.

APPLICATION — G1

Read the nine edges of G1 off the drawing: a–b, b–d, a–c, c–f, d–e, e–f, a–e, b–f and c–d. That is six vertices, nine edges, and every vertex of degree 3. Listing each vertex against its neighbours makes the structure visible:

Each of a, d and f is joined to all three of b, c and e and to nothing else, and symmetrically each of b, c and e is joined to all three of a, d and f. That is precisely the complete bipartite graph K3,3 with parts {a, d, f} and {b, c, e} — one of the two Kuratowski graphs. So G1 is not planar, and the two crossings in its drawing are forced by the structure rather than by the layout.

APPLICATION — G2

G2 has six vertices and twelve edges. Naming its vertices by drawn position — P top-left, Q top-right, L left, R right, S bottom-left, T bottom-right — the edges are L–P, L–Q, L–R, L–S, L–T, P–R, P–S, P–T, Q–R, Q–T, S–R and T–R. A crossing-free drawing can be built in three steps:

1. L, R, P and T are mutually adjacent (L–R, L–P, L–T, P–R, P–T and R–T are all present), so they induce a K4. Draw it flat: triangle L–R–P with T placed inside it. Its four regions are the triangles LRT, LPT, RPT and the outer region LRP.

2. Q is joined to exactly L, R and T. Place Q inside the triangular region LRT and run its three edges to that region’s corners; no crossing is created.

3. S is joined to exactly L, R and P. Place S in the outer region LRP and run its three edges to those corners; again no crossing is created.

All six vertices and all twelve edges are now drawn with no crossing, so G2 is planar. It is in fact a maximal planar graph: with v = 6 and e = 12 it sits exactly on the bound e = 3v − 6, so the drawing is a triangulation whose 8 regions are all triangles.

CROSS-CHECK

• The edge bound e ≤ 3v − 6 is necessary but never sufficient. G1 has v = 6 and e = 9 ≤ 12, so it passes the bound and is still non-planar; only the Kuratowski subgraph settles it. Counting edges can rule a graph out, never in.

• G2 admits no K5 subdivision either: such a subdivision needs five branch vertices of degree at least 4, and G2’s degree sequence is 5, 5, 4, 4, 3, 3 — just four vertices reach degree 4.

• Euler’s formula confirms the G2 drawing: v − e + f = 6 − 12 + 8 = 2, exactly as a plane triangulation on six vertices requires.

RESULT

G1 is not planar — it is K3,3 itself — while G2 is planar, being a six-vertex plane triangulation.