Connectivity and Plane Drawings
In a plane graph, the placement of edges is constrained not only by crossings but also by the vertices through which different parts of the graph attach. A vertex whose deletion disconnects a graph is an especially narrow bottleneck. A pair of vertices can play the same role even when neither vertex alone does. Three-connectivity rules out both kinds of bottleneck: after deleting any one or two vertices, the remaining graph must still be connected. This condition has a direct geometric consequence. A simple closed curve that meets a plane drawing only at one or two vertices cannot leave graph vertices on both sides.
All graphs here are finite and simple. For \(S\subseteq V(G)\), \(G-S\) denotes the graph obtained by deleting the vertices in \(S\) and every edge incident with them. A graph is connected if every pair of its vertices can be joined by a path. A vertex cut is a set \(S\) whose deletion disconnects the graph. This is different from an edge cut, which is a set of edges whose deletion disconnects it.
A plane embedding is a drawing of a graph in the plane in which vertices are distinct points and edges are arcs meeting one another only at common endpoints. A graph is planar if it has at least one plane embedding; a plane graph means a graph together with a particular embedding. Connectivity is a property of the abstract graph, while the locations of its vertices and edges belong to the embedding.
A Necessary Degree Condition
Proof. Let \(G\) be 3-connected and let \(v\in V(G)\). Suppose \(\deg(v)\le 2\), and let \(S=N(v)\), the set of vertices adjacent to \(v\). Then \(|S|\le 2\). By 3-connectivity, \(G-S\) is connected. It contains \(v\), and it also contains at least one other vertex: since \(|V(G)|\ge4\), deleting at most two vertices other than \(v\) leaves at least one vertex besides \(v\). But \(v\) has no neighbors in \(G-S\), so it cannot be joined to that other vertex by a path. This contradicts connectedness of \(G-S\). Hence \(\deg(v)\ge3\), as required. \(\square\)
The condition is necessary, not sufficient. A graph can have minimum degree at least three and still have a two-vertex cut. That distinction matters in plane embeddings: degree measures the number of edges incident with a vertex, whereas a separator measures whether deleting vertices breaks the rest of the graph apart.
What Separators Mean in a Plane Embedding
The geometric link comes from the Jordan curve theorem: a simple closed curve in the plane separates the plane into two regions, and any continuous path from one region to the other meets the curve. We use this standard topological result in the following precise form.
Proof. Let \(x\) and \(y\) be vertices of \(G-S\) on opposite sides of \(C\). If there were an \(x\)-\(y\) path in \(G-S\), its drawing would give a continuous route from one side of \(C\) to the other. By the Jordan curve theorem, that route must meet \(C\). But the drawing meets \(C\) only at vertices in \(S\), and a path in \(G-S\) uses no vertex of \(S\). This is a contradiction. Thus \(x\) and \(y\) are in different components of \(G-S\), so \(S\) is a vertex cut. If \(G\) is 3-connected, no set of at most two vertices can be a vertex cut, so the stated configuration is impossible. \(\square\)
This gives a useful way to read a drawing. If a curve passing through two vertices separates substantial parts of the graph, those vertices are a separator. In a 2-connected graph this can occur: 2-connectivity only rules out separation caused by deleting one vertex. In a 3-connected graph it cannot occur. This does not by itself describe every possible embedding, nor does it imply that every curve through two vertices is forbidden: the proposition requires graph vertices on both sides and no other intersection between the curve and the drawing.
Worked Examples
Worked Example: A Planar 2-Connected Graph with a Two-Vertex Cut
Let \(G\) have vertex set \(V=\{u,v,x,y,z\}\) and edge set \(E=\{ux,uy,vx,vy,xz,yz\}\). This is \(K_{2,3}\), with parts \(\{u,v\}\) and \(\{x,y,z\}\). Determine its connectivity and describe a plane embedding.
Deleting \(u\) leaves the edges \(vx,vy\), together with \(xz,yz\), so every remaining vertex is joined to \(v\): \(x\) and \(y\) are adjacent to \(v\), and \(z\) is joined to \(x\) and \(y\). The remaining graph is connected. The same reasoning applies after deleting \(v\). If instead \(x\) is deleted, the remaining graph has edges \(uy,vy,yz\), so all four remaining vertices are connected through \(y\). Deleting \(y\) leaves the connected graph with edges \(ux,vx,xz\), and deleting \(z\) leaves the connected graph with edges \(ux,uy,vx,vy\). Thus deleting any one vertex leaves a connected graph: \(G\) is 2-connected.
Deleting the pair \(\{u,v\}\) leaves three vertices \(x,y,z\) and no edges among them. The remaining graph is disconnected, so \(\{u,v\}\) is a vertex cut and \(G\) is not 3-connected.
For a plane embedding, draw the three paths \(u-x-v\), \(u-y-v\), and \(u-z-v\) as three noncrossing arcs from \(u\) to \(v\), with their internal vertices distinct. These paths divide the plane into regions without crossings. The pair \(\{u,v\}\) is exactly the common attachment set for the three internal vertices: deleting it separates them.
Check: the graph has six listed edges, and each of \(u,v\) has degree \(3\), while \(x,y,z\) each have degree \(2\). The degree condition for 3-connectivity detects the failure here as well, but the explicit deletion of \(\{u,v\}\) identifies the separator itself.
Worked Example: A Planar 3-Connected Graph
Let \(H\) have vertex set \(V=\{a,b,c,d,e\}\) and edge set consisting of all pairs of distinct vertices except \(ab\). Equivalently, \(E=\{ac,ad,ae,bc,bd,be,cd,ce,de\}\). Verify that \(H\) is 3-connected and planar.
Consider deleting a set \(S\) with \(|S|\le2\). If both \(a\) and \(b\) remain, then at most one of \(c,d,e\) has been deleted. At least two of \(c,d,e\) remain, and each remaining one is adjacent to both \(a\) and \(b\). The remaining graph is connected: every remaining vertex among \(c,d,e\) is adjacent to both \(a\) and \(b\), and any two such vertices are adjacent to each other.
If \(a\) or \(b\) does not remain, then at most one of them remains. The other three remaining vertices must include vertices from \(\{c,d,e\}\), and those vertices are pairwise adjacent. If \(a\) remains, it is adjacent to each of \(c,d,e\); if \(b\) remains, it is also adjacent to each of \(c,d,e\). Therefore the remaining graph is connected in this case too. This proves that deleting any set of at most two vertices leaves a connected graph, so \(H\) is 3-connected.
To embed \(H\) in the plane, draw the triangle with vertices \(c,d,e\). Place \(a\) inside the triangle and join it to \(c,d,e\) without crossings. Place \(b\) outside the triangle and join it to \(c,d,e\) in the exterior, again without crossings. The six edges incident with \(a\) or \(b\) are precisely \(ac,ad,ae,bc,bd,be\), and the three edges of the triangle are \(cd,ce,de\); these are all nine edges of \(H\).
Check: there are \(\binom{5}{2}=10\) possible pairs of vertices, and exactly one, \(ab\), is absent, so \(|E(H)|=10-1=9\), matching the edge list. The deletion argument checked both possibilities—whether both \(a,b\) remain or at least one is deleted—so it covers every set of size at most two.
Worked Example: Minimum Degree Three Is Not Enough
Let \(F\) be the union of two complete graphs on four vertices that share exactly the edge \(pq\). Explicitly, take \(V=\{p,q,r,s,t,w\}\) and \(E=\{pq,pr,ps,qr,qs,rs,pt,pw,qt,qw,tw\}\). Show that \(F\) has minimum degree three but is not 3-connected.
The degrees are \(\deg(p)=5\), since \(p\) is adjacent to \(q,r,s,t,w\); \(\deg(q)=5\), since \(q\) has the same five neighbors; and \(\deg(r)=\deg(s)=\deg(t)=\deg(w)=3\). Thus \(\delta(F)=3\).
After deleting \(p\) and \(q\), the remaining vertex set is \(\{r,s,t,w\}\), and the remaining edges are \(rs\) and \(tw\). There is no edge joining \(\{r,s\}\) to \(\{t,w\}\), so \(F-\{p,q\}\) is disconnected. Hence \(F\) is not 3-connected, despite its minimum degree being three.
The graph is planar: draw one copy of \(K_4\) with \(pq\) on the boundary of a region, and draw the other copy on the other side of \(pq\). Each copy can be drawn without crossings, so the combined drawing has none. The example shows why vertex deletion tests, rather than degree alone, are needed.
Check: the edge list has \(6+6-1=11\) edges: each \(K_4\) contributes six, and the shared edge \(pq\) is counted in both lists, so it is subtracted once. This agrees with the displayed edge set.
How to Use the Definition
For a finite graph, the definition gives a direct test: examine the graphs obtained by deleting each set of zero, one, or two vertices, and check that every one is connected. The number of tests can grow with the order of the graph, but this definition is the right standard for reasoning about separators.
A disconnected graph is not 3-connected. It also fails the deletion condition for \(S=\varnothing\).
If some \(G-v\) is disconnected, then \(v\) is a vertex cut and the graph is not 3-connected.
If some \(G-\{u,v\}\) is disconnected, then \(\{u,v\}\) is a vertex cut and the graph is not 3-connected.
A simple closed curve meeting the drawing only at one or two vertices and leaving graph vertices on both sides exhibits a forbidden separator in a 3-connected graph.
A common mistake is to treat a degree check as a complete connectivity test. For example, the incorrect inference “\(\delta(F)=3\), therefore \(F\) is 3-connected” fails for the graph in the third example: \(\delta(F)=3\), but \(F-\{p,q\}\) has two components. The correction is to use \(\delta(G)\ge3\) only as a necessary condition and then check the vertex deletions required by the definition.
The distinction is useful when studying plane graphs because a small vertex separator allows different portions of the graph to meet at only a few attachment points. Three-connectivity rules out that bottleneck. The curve proposition makes this constraint visible in an embedding without requiring a full description of the regions or their boundary walks.
Check Your Understanding
Use the deletion definition and the plane-curve proposition to justify each answer.
- Explain why a graph on four vertices cannot be 3-connected if one vertex has degree two.
- For \(K_{2,3}\), which pair of vertices is a cut, and what components remain after deleting it?
- Why does \(\delta(G)\ge3\) not, by itself, prove that \(G\) is 3-connected?
- Suppose a simple closed curve meets a plane drawing only at two vertices and has graph vertices on both sides. What can be concluded about those two vertices?
- State the difference between a vertex cut and an edge cut.