Plane Embeddings of K4 and K2,3

From Planar Graphs to Plane Embeddings

A graph is planar if it can be drawn in the plane with no edge crossings. A particular crossing-free drawing is a plane embedding: vertices are represented by distinct points, and edges by arcs joining their endpoints, with two arcs meeting only at a shared endpoint. A plane embedding has faces, the regions into which the drawing divides the plane; the unbounded region is one of the faces. The boundary of a face is described by the edges and vertices encountered while tracing its boundary.

Here the goal is constructive: give explicit embeddings of \(K_4\) and \(K_{2,3}\), then verify their faces rather than relying on a picture. In particular, an embedding must account for the unbounded face as well as the bounded ones. We use the earlier result that every connected plane graph satisfies Euler’s formula \(n-m+f=2\), where \(n\) is the number of vertices, \(m\) the number of edges, and \(f\) counts all faces, including the unbounded face.

An Embedding of \(K_4\)

Proof. The specified edge set contains all six pairs of distinct vertices, so the graph drawn is \(K_4\). The triangle with vertices \(1,2,3\) has no crossing edges on its boundary. Vertex \(4\) is strictly inside that triangle, and its three incident segments lie within the triangle apart from their endpoints. Since these segments have distinct directions from \(4\), they meet one another only at \(4\). They divide the triangle’s interior into exactly the three regions bounded by \(1241\), \(2342\), and \(3143\); the region outside the triangle is the unbounded face, bounded by \(1231\). Therefore the drawing has no crossings and has exactly the stated faces. \(\square\)

To audit the face list edge by edge, \(12\) occurs in \(1231\) and \(1241\); \(23\) occurs in \(1231\) and \(2342\); and \(13\) occurs in \(1231\) and \(3143\). The remaining edges \(14,24,34\) each occur on two of the three bounded triangular faces. Thus every edge appears twice in the complete list of face boundaries.

An Embedding of \(K_{2,3}\)

Proof. Each of \(x,y,z\) is joined to both \(a\) and \(b\), and there are no other edges, so the edge set is exactly that of \(K_{2,3}\) with parts \(\{a,b\}\) and \(\{x,y,z\}\). In the specified coordinates, the interiors of the segments on the path \(a,x,b\) have positive vertical coordinate, those on \(a,y,b\) have vertical coordinate zero, and those on \(a,z,b\) have negative vertical coordinate. Within each path, its two segments meet at its intermediate vertex. Between different paths, segments meet only at \(a\) or \(b\). Thus there are no crossings. The three paths in their vertical order enclose the two regions between consecutive paths; the remaining region is unbounded and lies outside the cycle formed by the upper and lower paths. These are exactly the three listed faces. \(\square\)

Checking Every Boundary

A face boundary can be checked in two complementary ways: verify that its consecutive vertices are adjacent, and verify that the complete face list accounts for the sides of all edges. These checks matter because a face count must include the unbounded region. For both embeddings, no face boundary repeats a vertex, so the boundary lengths can be read directly from the listed cycles.

This audit also identifies why the unbounded face is not an optional extra. The outer cycle \(a,x,b,z,a\) bounds the exterior face in the plane drawing; the middle path \(a,y,b\) lies inside that cycle and separates its interior into two bounded faces. The exterior counts as one face, not zero, and the region inside the outer cycle is not itself a single additional face.

Using Euler’s Formula as a Check

For a connected plane embedding, Euler’s formula is \(n-m+f=2\), with \(f\) counting all regions, bounded and unbounded. Both graphs here are connected: every vertex in either graph is joined by a path to every other vertex. The formula therefore applies to both constructions. It checks the face count obtained from the geometry, but it does not by itself identify the face boundaries; those must still be read from the embedding.

For \(K_4\), the counts are \(n=4\), \(m=6\), and \(f=4\), so \(4-6+4=2\). For \(K_{2,3}\), they are \(n=5\), \(m=6\), and \(f=3\), so \(5-6+3=2\). In each case the sum of face-boundary lengths is \(2m\): the four triangular boundaries of \(K_4\) sum to \(4\cdot3=12=2\cdot6\), and the three quadrilateral boundaries of \(K_{2,3}\) sum to \(3\cdot4=12=2\cdot6\).

These are two different checks. Euler’s formula checks the total number of faces for a connected plane graph. The edge-face incidence count checks that the boundaries use each edge side consistently. Neither substitutes for giving a crossing-free drawing and a complete face list.

Common Pitfall: Adding a Face Twice

A frequent error is to list the bounded faces of \(K_{2,3}\), then count the region inside the outer cycle as an additional face, and finally count the unbounded region as well. In the embedding above, the bounded faces are already the regions between the upper and middle paths and between the middle and lower paths. The remaining region is the unbounded face. There are three faces, not four.

The incorrect count would give \(n-m+f=5-6+4=3\), which contradicts Euler’s formula for this connected plane graph. It also fails the boundary-length check: if four faces were incorrectly assigned length \(4\), the sum would be \(4\cdot4=16\), but the six edges have only \(2\cdot6=12\) sides in total. Count each region once, and include the unbounded one exactly once.