Planar Graph Cycle Proof (boundary walk question)

75 Views Asked by At

Prove that if G is a 2-connected plane graph, then the boundary walk of every face of G describes a cycle.

What does this question mean by boundary walk? I have tried looking it up but do not quite understand. My understanding is it is just the cycle around a bounded region but not sure how that relates.

1

There are 1 best solutions below

0
On BEST ANSWER

The understanding "the cycle around a bounded region" is not exactly wrong, but missing the nuance you'll need to think about the problem.

Here's an example of a plane graph with faces $F_1, F_2, F_3$:

planar graph

Face $F_1$ is a very normal face. Its boundary walk is just the cycle $(3,7,8,3)$ formed by the edges separating $F_1$ from the rest of the graph.

The unbounded face $F_3$ also has a very normal boundary walk: it is the cycle $(1,2,3,4,5,6,1)$.

However, if you look at the boundary walk of face $F_2$ - also formed by the edges separating it from the rest of the graph - you'll get the walk $(1,2,3,7,8,3,4,5,6,1)$, which is not a cycle, because it revisits vertex $3$. (A cycle is not supposed to revisit a vertex, aside from how the end is the same as the start.)

In general, imagine the plane graph as the floor plan of a building; the edges are the walls, and the faces are the rooms. To get the boundary walk of a face, you put your hand on a wall and start following that wall until you return to the place you started; the boundary walk is the closed walk in the graph representing your trajectory.

(This intuition, and the whole notion of boundary walks of faces, is only valid for connected graphs; if the graph is not connected, then a face might have multiple boundaries.)