Planar Graphs

Draw $K_4$ on vertices $1,2,3,4$ as a square with both diagonals: the four sides $12,23,34,41$ and the two diagonals $13,24$. The diagonals cross in the middle of the picture. Redraw instead as an outer triangle $1,2,3$ with $4$ placed inside it, joined to each corner: now all $6$ edges ($12,23,31,14,24,34$) are present and no two cross. $K_4$ is planar — the crossing was a flaw of the FIRST picture, not of the graph.

Let $K_{2,3}$ have parts $X = \{a,b\}$ and $Y = \{1,2,3\}$, all $6$ cross edges. Place $a$ above and $b$ below a row of $1, 2, 3$: $a$ reaches down to each of $1,2,3$, $b$ reaches up to each of $1,2,3$, and no two of the six segments meet except at a shared endpoint. So $K_{2,3}$ is planar, and the same trick draws any $K_{2,n}$ without crossings.

Three houses $\{1,2,3\}$ each need gas, water and electricity from utilities $\{g,w,e\}$ — every house joined to every utility, the graph $K_{3,3}$. Try the $K_{2,3}$ trick: houses in a row above, utilities in a row below. Now EVERY house must reach EVERY utility, not just two special vertices reaching everybody, and the straight-line picture already draws all $9$ edges with several crossings, for instance $1w$ crossing $2g$. Does some cleverer drawing avoid every crossing instead? The question is settled later in this topic, in K_5, K_3,3 and Kuratowski's Theorem.

A star with hub $h$ and four leaves $1,2,3,4$ (edges $h1,h2,h3,h4$) is a tree: $V=5$, $E=4$. A tree has no cycle to enclose a region, so the whole plane outside the drawing is one single face: $F=1$. Check: $5 - 4 + 1 = 2$, exactly as the formula demands.

Return to $K_4$ drawn as a triangle $1,2,3$ with $4$ inside (Planar Graphs and Plane Drawings): $V=4$, $E=6$. The drawing cuts the inside of the triangle into the three small triangles $124, 234, 134$, plus the outer face outside triangle $123$ — $F=4$. Check: $4-6+4=2$.

A connected plane graph has $12$ vertices and $20$ edges. How many faces does it have? Solve Euler's Formula for $F$: $F = 2 - V + E = 2 - 12 + 20 = 10$. No picture is needed — the formula alone pins down the face count once $V$ and $E$ are known, for ANY connected plane drawing of the graph, however it is drawn.

Take the pentagon $1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}1$ with one added chord $13$: $V=5$, $E=6$. The chord cuts the inside into a triangle $123$ (length $3$) and a quadrilateral $1345$ (length $4$); together with the outer face, whose boundary is the whole pentagon (length $5$), the three face-lengths are $3+4+5=12=2E$, confirming each edge is counted on exactly two faces (the chord $13$ borders the triangle and the quadrilateral; every pentagon side borders the outer face and one inner face).

$K_5$ has $V=5$ and $E=\binom{5}{2}=10$. The bound allows at most $3(5)-6=9$ edges for a planar graph on $5$ vertices, and $10 > 9$: $K_5$ is not planar.

$K_{3,3}$ is bipartite with $V=6$ and $E=9$. The bipartite bound allows at most $2(6)-4=8$ edges, and $9>8$: $K_{3,3}$ is not planar either — a different, sharper bound catching a graph the plain bound would not (since $3(6)-6=12\ge9$ says nothing).

The Petersen graph has $V=10$, $E=15$, and girth $5$ (its shortest cycle has length $5$ — the outer $5$-cycle $o_1\text{-}o_2\text{-}o_3\text{-}o_4\text{-}o_5\text{-}o_1$ is one, and no shorter cycle exists anywhere in the graph). The girth-$5$ bound gives $E \le \frac{5}{3}(10-2) = \frac{40}{3} \approx 13.3$, yet $E=15$. Even this generous bound is violated: the Petersen graph is not planar.

Take $K_{3,3}$ on $X=\{a,b,c\}$, $Y=\{1,2,3\}$ and subdivide the single edge $a1$: delete it and add a new vertex $x$ with edges $ax$, $x1$. The result has $V=7$, $E=10$ — one more of each than $K_{3,3}$ — and $x$ has degree exactly $2$, as a subdivision vertex must. Contracting $x$ back out (deleting it and joining $a$ to $1$ directly) exactly recovers $K_{3,3}$, confirming this new graph IS a subdivision of $K_{3,3}$, and so, by Kuratowski's Theorem, is non-planar too, even though it is not literally $K_{3,3}$.

The Petersen graph has an outer $5$-cycle $o_1,\ldots,o_5$, an inner pentagram $i_1,\ldots,i_5$ (edges $i_1i_3,i_3i_5,i_5i_2,i_2i_4,i_4i_1$) and spokes $o_ki_k$ (Topic 1). Take $X=\{o_1,o_3,i_4\}$ and $Y=\{o_2,o_4,i_1\}$. Nine paths join every $X$-vertex to every $Y$-vertex, using only $o_5,i_2,i_3$ as intermediate (degree-$2$) vertices, with $i_5$ left unused:

All nine are internally disjoint — no two share an intermediate vertex, and no intermediate vertex is itself one of the six branch vertices — so this is a genuine subdivision of $K_{3,3}$ hiding inside the Petersen graph. By Kuratowski's Theorem the Petersen graph is not planar, confirming the girth bound from the previous section by a completely different argument.

Draw $K_4$ as a triangle $1,2,3$ with $4$ inside (as before): $4$ faces, the three inner triangles $f_1=124$, $f_2=234$, $f_3=134$, and the outer face $f_0=123$. Build the dual: put one dual vertex in each face and join two dual vertices whenever their faces share an edge. $f_0$ shares edges with all three inner faces ($12$, $23$, $31$), and each pair of inner faces shares one spoke ($f_1,f_2$ share $24$; $f_2,f_3$ share $34$; $f_1,f_3$ share $14$). So every dual vertex is joined to the other three — the dual is $K_4$ again, on $4$ vertices and $6$ edges, matching $V(K_4^*)=F(K_4)=4$ and $E(K_4^*)=E(K_4)=6$.

A convex polyhedron has $20$ faces, every one a triangle, and every vertex surrounded by exactly $5$ faces (so degree $5$). Each triangular face has $3$ edges and each edge is shared by exactly $2$ faces, so $E = 3F/2 = 3(20)/2=30$. Each vertex has degree $5$, so by the handshake lemma (Topic 1) $E = 5V/2$, giving $V = 2E/5 = 2(30)/5=12$. Check with Euler's Formula: $V-E+F = 12-30+20=2$. This is exactly the icosahedron: $12$ vertices, $30$ edges, $20$ triangular faces.