Planarity Under Deletion and Contraction

Planarity and Graph Operations

A graph is planar when it can be drawn in the plane without crossings. Starting from such a drawing, deleting vertices or edges seems harmless: simply remove the corresponding parts. Contracting an edge requires a more careful modification, because it identifies two vertices and changes how their incident edges meet. The key fact is that this identification can be made inside a small region around the edge, leaving the rest of the drawing unchanged.

All graphs in this tutorial are finite and simple unless stated otherwise. A plane embedding of a graph represents each vertex by a distinct point and each edge by a simple arc between its endpoints, with edge interiors disjoint from one another and from all vertices. A graph is planar if it has at least one plane embedding. Thus a plane embedding is a particular drawing, whereas planarity is a property of the abstract graph.

In a contraction, an edge from \(u\) to a third vertex \(w\) and an edge from \(v\) to that same \(w\) both become edges from \(x\) to \(w\). These are parallel in the intermediate drawing; the simple contracted graph retains one. The graph conventions here exclude loops. For a simple graph, contracting \(uv\) creates no loop other than the contracted edge itself, which is removed.

Deletion in a Plane Embedding

Proof. Choose a plane embedding of \(G\). For \(G-e\), remove the arc representing \(e\), leaving every other vertex and edge arc in place. The remaining arcs still meet only at common endpoints, so they form a plane embedding of \(G-e\). For \(G-v\), remove the point representing \(v\) and the arcs of all edges incident with \(v\). Every remaining edge arc has the same endpoints as before, and no new intersection is introduced. The result is a plane embedding of \(G-v\). This reasoning also covers an isolated vertex: deleting it simply removes its point. If the graph has no vertices, there is nothing to remove, and it is already planar. \(\square\)

Contracting an Edge in a Plane Embedding

For contraction, the central geometric step is to modify the drawing only near the edge being contracted. In a plane embedding, choose a small closed disk around the arc for \(uv\) and its endpoints. The disk can be chosen so that it contains no other vertices and meets each other incident edge only in a short initial segment near \(u\) or \(v\). Its boundary then has one point for each such incident edge segment. Outside the disk, leave the embedding unchanged.

Remove the parts of the drawing inside the disk and place a single point \(x\) there. Join \(x\) to each boundary point by arcs whose interiors are disjoint. Such arcs can be drawn as spokes from an interior point of a disk to its boundary points; they meet one another only at \(x\). Continue each spoke along the corresponding unchanged edge segment outside the disk. The former edge \(uv\) is gone, and the two endpoints have become \(x\). If two of the resulting edges have the same other endpoint, erase all but one. Removing duplicate arcs cannot introduce a crossing.

Proof. Fix a plane embedding of \(G\) and choose a disk as described above around the embedded edge \(uv\) and its endpoints. If no other edge is incident with either endpoint, replace the part of the drawing in the disk by one isolated vertex; the unchanged outside drawing still has no crossings. Otherwise, replace the drawing inside the disk by a point \(x\) joined to each boundary point by spokes with disjoint interiors. The spokes meet each other only at \(x\), and they meet the unchanged outside drawing only at their respective boundary points. Thus the new drawing has no crossings and represents the graph in which \(u\) and \(v\) are identified and \(uv\) is removed. If multiple edges have become parallel, erase all but one of each set of parallel edges. The resulting drawing is a plane embedding of the simple contracted graph. \(\square\)

This argument establishes existence of an embedding after contraction; it does not require that the original embedding have a special shape. If contracting an edge leaves a graph with an isolated vertex, that vertex is represented by a point, as usual. The construction is local, so all parts of the original drawing outside the chosen disk remain undisturbed.

Repeated Operations and What the Result Does Not Say

Proof. Begin with a plane embedding of the original planar graph. After each operation, the deletion proposition or contraction theorem gives a plane embedding of the resulting graph. Applying this reasoning successively to each operation in the finite sequence proves that the final graph is planar. A sequence of length zero leaves the original planar graph unchanged, so that case also holds. \(\square\)

The result is one-way: these operations preserve planarity when applied to a planar graph. It does not say that undoing an operation preserves planarity. For instance, \(K_5\) is nonplanar, as established in earlier material, but contracting any edge of \(K_5\) and simplifying gives \(K_4\). To check the graph calculation, label the contracted endpoints \(1,2\) and call the merged vertex \(x\). The other vertices are \(3,4,5\); the result has all six edges \(x3,x4,x5,34,35,45\), so it is \(K_4\), which has a plane embedding. Thus a planar contracted graph does not imply that the graph before contraction was planar.

Common Pitfall

A common error is to treat contraction as edge deletion. For the cycle with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), deleting \(12\) leaves four vertices and the three edges \(23,34,41\). Contracting \(12\), however, identifies two vertices: it gives \(V=\{x,3,4\}\) and \(E=\{x3,34,4x\}\). The vertex count drops from four to three, and the two edges formerly incident with \(1\) and \(2\) are reattached to \(x\). A contraction is not simply a removal of an edge; it changes the endpoint structure of the remaining edges.

Another error is to assume that the intermediate result of contraction must already be simple. It may have parallel edges, as the \(K_4\) example shows. The embedding argument first permits these arcs to meet at their shared endpoints; the simple contracted graph is then obtained by deleting duplicate edges. Since edge deletion preserves planarity, the simplification is valid.