Planar Graphs and Kuratowski's Theorem: Homeomorphism, K5 and K3,3 Worked Examples

A crossing in a sketch can mislead you: it may disappear after a redraw. The reverse trap is subtler. A graph can pass the usual edge-count test and still contain a forbidden nonplanar structure. For GATE CS preparation, you need a method that separates the drawing from the graph itself. Redrawing, arithmetic screens and Kuratowski's theorem expose whether a hidden obstruction is present.

Planar graph, plane graph and crossing: fix the language first

A planar graph is an abstract graph that has at least one drawing in the plane where edges meet only at common endpoints. A plane graph is one particular crossing-free embedding of a planar graph. Its regions, including the outer region, are faces. Planarity therefore belongs to the graph, not to the first picture you see.

Take K4 with vertices {A,B,C,D} and edges {AB,AC,AD,BC,BD,CD}. Draw the cycle A-B-C-D-A as a square and add diagonals AC and BD. The diagonals cross, but that crossing is not a vertex. Now draw A,B,C as an outer triangle, put D inside, and join D to all three outer vertices. There are no crossings. Here V=4, E=6 and F=4, so V-E+F=4-6+4=2. From this language, move on to the wider properties in Graph Theory: Euler, Hamiltonian, Coloring for GATE CS, without assuming that Eulerian or Hamiltonian implies planar.

Use Euler and edge bounds as screens, not complete tests

For a connected plane graph, Euler's formula is V-E+F=2. Counting edge appearances around faces gives two useful necessary conditions for a simple connected planar graph with V>=3. In general, E<=3V-6. If the graph is bipartite, every facial boundary has length at least four, so the sharper condition is E<=2V-4.

Violating a bound proves nonplanarity. Satisfying one proves nothing by itself. For K5, V=5 and E=10, while 3V-6=3(5)-6=9. Since 10>9, K5 is nonplanar. For K3,3, V=6 and E=9. The general check gives 9<=3(6)-6=12, which is inconclusive. Because K3,3 is bipartite, use the sharper bound: 2V-4=2(6)-4=8, and 9>8 proves nonplanarity. If you want a wider mathematics route alongside this topic, Engineering Mathematics for GATE covers broader GATE mathematics preparation.

Kuratowski's theorem and what homeomorphism means

Kuratowski's theorem says that a finite graph is planar if and only if it contains no subgraph that is a subdivision of K5 or K3,3. Here K5 is the complete graph on five vertices, so every vertex has degree four. K3,3 is the complete bipartite graph with two parts of three vertices each, so every branch vertex has degree three.

A subdivision replaces an edge uv by a path such as u-x-v, where the new vertex x has degree two. Repeating that local move produces a graph homeomorphic to the original. Suppressing a degree-two subdivision vertex reverses the move. The forbidden structure needs to be only a subgraph, so you may first delete unused vertices and edges.

The word is homeomorphism, not homomorphism. A graph homomorphism is an adjacency-preserving map between vertex sets, and it is not Kuratowski's planarity test. Edge contraction appears in the minor characterisation of planarity, but contraction is not the homeomorphism operation used in this theorem.

Worked example: suppress a hidden subdivision and recover K3,3

Define graph H with vertices

{u1,u2,u3,v1,v2,v3,x,y}

and edges

{u1x,xy,yv1,u1v2,u1v3,u2v1,u2v2,u2v3,u3v1,u3v2,u3v3}.

Each of u1,u2,u3,v1,v2,v3 has degree three. Vertices x and y each have degree two. The degree sum is therefore 6 x 3 + 2 x 2 = 18+4=22. By the handshaking lemma, 2E=22, so E=11; also, V=8.

Counting does not settle planarity. The general bound gives 11<=3(8)-6=18. Graph H is bipartite with parts {u1,u2,u3,y} and {v1,v2,v3,x}, but it also passes the bipartite bound: 11<=2(8)-4=12. Both results are inconclusive, not evidence that H is planar.

Now reverse the subdivisions one at a time:

1. Vertex x has neighbours u1 and y. Suppress x by replacing edges u1x,xy with the single edge u1y.

2. Vertex y now has neighbours u1 and v1. Suppress y by replacing u1y,yv1 with u1v1.

The counts trace the same reversal. Suppressing x removes one vertex and replaces two edges with one, leaving V=7 and E=10. Suppressing y does the same again, leaving V=6 and E=9, exactly the counts of K3,3. More importantly, endpoint connection u1-v1 is restored.

Six vertices remain. For every i,j in {1,2,3}, the edge uivj is present, and no edge lies within either part. The remaining graph is exactly K3,3 with parts {u1,u2,u3} and {v1,v2,v3}.

The conclusion is structural: H is a subdivision of K3,3; therefore H is homeomorphic to a Kuratowski obstruction; therefore H is nonplanar. The degree-two vertices did not cause nonplanarity by themselves. Their path preserved the connection between the correct branch vertices.

A reliable decision workflow for planarity questions

Use this order instead of jumping from a messy picture to a verdict:

1. Read the vertices and adjacencies. Do not trust the geometry of the given drawing.

2. Attempt a crossing-free redraw, as with K4.

3. Count V and E. Apply E<=3V-6, then apply E<=2V-4 only after establishing bipartiteness.

4. While seeking a forbidden subgraph, delete irrelevant leaves or extra edges and suppress degree-two chains without changing their endpoints.

5. Compare the remaining branch-vertex pattern with K5 and K3,3.

A crossing-free embedding proves planar. A violated necessary bound proves nonplanar. An exhibited subdivision of K5 or K3,3 also proves nonplanar. A passed bound means only “inconclusive”. For example, add a new leaf z and edge zu2 to H. When selecting the Kuratowski subgraph, delete z and zu2. The original K3,3 subdivision remains, so the larger graph is still nonplanar.

Traps that make a plausible proof invalid

Pair each tempting shortcut with its repair:

• “The shown edges cross” must become “try another embedding”. The crossed square drawing of K4 becomes crossing-free after redrawing.

• “E<=3V-6, so the graph is planar” must become “the necessary screen passed; inspect the structure”. Graph H passes both bounds and still suppresses to K3,3.

• “I cannot see an induced K3,3” must become “look for a subgraph that is a subdivision”. Kuratowski's theorem does not require an induced copy.

• “Homomorphism preserves planarity” must become “use homeomorphism through subdivisions”. Degree-two vertices help only when their paths join the correct branch vertices.

Extra vertices and edges outside a selected K5 or K3,3 subdivision cannot rescue the graph. Also keep Euler's formula in scope: use V-E+F=2 for a connected plane embedding as stated here. Do not count supposed faces in a drawing that still contains crossings.

How exam-style questions test the same ideas

Four rapid checks:

• A simple graph has V=7,E=16. Since 3V-6=3(7)-6=15 and 16>15, it is nonplanar.

• A simple bipartite graph has V=8,E=13. Since 2V-4=2(8)-4=12 and 13>12, it is nonplanar.

• Graph H has V=8,E=11. It satisfies 11<=18 and 11<=12, so the numerical conclusion is “inconclusive”.

• Suppressing x and y in H recovers exactly K3,3, so the structural conclusion is nonplanar.

For terminology, replacing uv by u-x-v is subdivision. An adjacency-preserving vertex map is a homomorphism, not the relation used in Kuratowski’s theorem. Before choosing an option, write one reason: a redraw, an inequality, or a named recovered obstruction. Then practise the distinction with Graph Theory MCQs: 12 Solved Euler, Coloring, Trees.

Short version and the next practice step

A crossing belongs to a drawing, so try to redraw first. Edge bounds can disprove planarity, but they cannot certify it. When the bounds pass, search for a subdivision and suppress degree-two chains to expose K5 or K3,3. Use that order consistently. In the worked graph, u1-x-y-v1 suppresses to u1-y-v1, then u1-v1, recovering K3,3. If you want a structured route through wider GATE CS preparation, continue with GATE Guidance by Sanchit Sir.