Why is every repeated vertex in the walk around the outer face of a finite planar graph a cut vertex?

134 Views Asked by At

Let G be a finite planar graph, then there is a natural walk around the outer (i.e. the unbounded) face of G. It might happen that a vertex v is visited more than once by this walk. Proof that this is a cut-vertex.

This is a task which might be obvious at first glance, but I wasn't able to do it rigorously, i.e. by citing any of the used arguments from a book and proving everything else. I would also be satisfied with a book which I could cite. Thx.

2

There are 2 best solutions below

0
On

Think about the edges of the walk as Jordan curves and the nodes as vertices. Suppose that you walk begins at the "repeated" vertex: $W=v_1 v_2 v_3 ..., v_k v_1 v_{k+1},...$ Note that if you union together the Jordan curves $v_1\to v_2\cup v_{2}\to v_{3}\cup ... \cup v_{k}\to v_{1}$ you get a closed curve. The closed curve divides the plane into two regions the inner (bounded) region and the outer (unbounded) region. View the vertices that you walked along, $v_1,...,v_{k}$ as being in the bounded face. There are possibly more vertices/edges in that bounded face, and $v_{k+1}$ is not in the bounded face. Then, all you need to see is that deleting $v_{k}$ separates $v_{k-1}$ from $v_{k+1}$. The reason for this is that no other vertex on the closed curve $v_1...v_{k}v_{1}$ can be visited twice (on the bigger walk around the outer face). If $v_{k-1}$ is not separated from $v_{k+1}$ then there is a path that goes from inside the bounded face to the outer face (but it must cross the boundary which it cannot do since the graph is planar).

0
On

The walk around a face $F$ is called the facial walk $W$ of $F$ in some parts of the literature (c.f. Graphs on Surfaces from Mohar and Thomassen). This walk has the property, that the "angle" at a given boundaryvertex of $F$ between an incoming edge and an outgoing edge of the walk contains no other edges. One could say the walk will always take the closest edge to its right. This angle is also "contained" in $F$. Now $F$ is path connected hence if you have a repeated vertex $v$, there are two angles $a$ and $b$ which you can connect by a path in the face, but you can also connect the endpoints of those paths to $v$. This gives you a closed Jordan Curve $J$. Now you have to proof that some Vertices of your graph are in the interior of $J$ and some are in the exterior. This can be done by observing that the two Vertices $w_1,w_2$ that "span" $a$ together with $v$ have to be contained in different components of $\mathbb R^2 \setminus J$ as they are connected by a path that crosses $J$ exactly once. Hence any path from $w_1$ to $w_2$ has to pass through $J$, but $J$ intersects the graph only in $v$. So the removal of $v$ will leave $w_1$ and $w_2$ in different Clusters of the graph.