Trees Have One Face in a Plane Embedding

Faces of an Embedded Tree

A tree has no cycles, but its drawing can still have complicated-looking branches and turns. The key fact is that no matter how a tree is drawn in the plane without crossings, its complement has just one connected region. In other words, every plane embedding of a tree has one face. The proof will delete a leaf and show that restoring its incident edge cannot split a face.

We work with finite simple graphs. A tree is a connected graph with no cycles. A plane embedding places distinct points for the vertices and draws each edge as a simple arc between its endpoints, with edge interiors disjoint from all vertices and from the interiors of other edges. To discuss the unbounded region on the same footing as the bounded ones, we can regard the plane as the sphere with one point omitted; the omitted point belongs to the unbounded face.

For the tree consisting of a single vertex, there are no edges. Removing that point from the sphere leaves a connected set, so this embedding has one face. For trees with edges, the argument depends on understanding what happens when an edge ends at a new leaf. The two sides of that edge are incident with the same face: the edge has a free end, so those sides can be joined by going around that end.

Why a Pendant Edge Does Not Split a Face

Proof. Let \(F\) be the complement of the embedded \(H\). By the assumption that \(H\) has one face, \(F\) is connected; it is also open in the sphere. The new edge, apart from its endpoint \(u\), lies inside \(F\) and ends at the new vertex \(v\). Removing this arc from \(F\) does not disconnect \(F\). To see why, take any two points of \(F\) not on the arc and join them by a path in \(F\). If that path crosses the arc, make a narrow detour alongside the arc. The two sides of the detour join around its free endpoint \(v\), so the crossing can be bypassed without leaving \(F\) or meeting the arc. Repeating this for the crossings gives a path avoiding the new edge and \(v\). Thus the complement after adding the edge and vertex remains connected, so there is still one face. \(\square\)

This is a local fact about the free endpoint. It does not say that adding any edge preserves the number of faces: an edge drawn between two existing vertices can close a cycle and split a face. A pendant edge has only one endpoint in the existing graph, so it does not form such a barrier.

The Leaf-Deletion Proof

Proof. We use induction on the number \(n\) of vertices. If \(n=1\), the embedded graph is a single point, and its complement in the sphere is connected. Hence it has one face.

Now let \(n\ge 2\), and assume the theorem holds for every tree with fewer than \(n\) vertices, in every plane embedding. We first justify that the given tree \(T\) has a leaf. Choose a path with as many vertices as possible, and let \(x\) be one of its endpoints. The vertex \(x\) has a neighbor, since \(T\) is connected and has at least two vertices. If \(x\) had a neighbor not on the path, the path could be extended, contradicting its maximal length. If \(x\) had another neighbor on the path besides the vertex next to it, that edge and the section of the path between its endpoints would form a cycle, contradicting that \(T\) is acyclic. Therefore \(x\) has degree one.

Delete \(x\) and its unique incident edge \(e\), and call the remaining embedded graph \(H=T-x\). It is acyclic because deleting vertices cannot create a cycle. It is connected because any two remaining vertices had a path between them in \(T\), and a degree-one vertex cannot be an internal vertex of a path between two other vertices. Thus \(H\) is a tree on \(n-1\) vertices. Its drawing, obtained by restricting the embedding of \(T\), is a plane embedding. By the induction hypothesis, \(H\) has one face. The deleted edge \(e\) joined a vertex of \(H\) to the new leaf \(x\), so the lemma shows that restoring \(e\) and \(x\) leaves one face. This proves the result for \(n\), and therefore for every finite tree. \(\square\)

The proof concerns the number of connected components of the complement, not the visual shape of the drawing. The tree may bend or branch in many places. At each induction step, the crucial feature is that the deleted edge has a free endpoint.

Worked Embedded Trees

A Common Face-Counting Mistake

Mistake: “Every edge has two sides, so a tree with three edges has six faces.” This confuses edge-sides with faces. Different edge-sides can be incident with the same face, and in a tree they are joined around leaf endpoints.

For a concrete correction, use the path on \(V=\{1,2,3\}\) with \(E=\{12,23\}\), drawn as two consecutive straight segments. The incorrect count assigns two faces to edge \(12\) and two more to edge \(23\), giving four faces. But the boundary walk is \(1,2,3,2,1\): it traverses each of the two edges twice while tracing one face. The theorem gives the same answer because the graph is a tree. Counting sides tells us how often edges occur on boundary walks; it does not, by itself, count distinct faces.

The one-face conclusion is useful because it supplies a reliable starting point for counting faces in more complicated connected plane graphs. A tree has no cycle to enclose a separate region, and leaf deletion formalizes why branches do not create one. To apply the result, first check that the graph is a tree and that the drawing is a plane embedding. A drawing with crossing edge interiors is not a plane embedding, so the theorem does not apply to that drawing as given.