I'm reading Richard J. Trudeau's book "Introduction to Graph Theory",
after defining polygonal
Definition 24. A graph is polygonal is it is planar, connected, and
has the property that every edge borders on two different faces.
from page 115 it defines "bridge" then talks about polygonal graph's boundary
Definition. A bridge in a graph is an edge whose removal would
increase the number of components.In a planar graph a bridge necessarily borders on only one face, and
an edge bordering on only one face is necessarily a bridge. Thus
bridges are the things that prevent planar connected graphs from being
polygonal. Use this fact to prove that if a planar and connected graph
G has the property that the boundary of every face is a cyclic graph,
then G is polygonal. Then show that the converse statement is false by
finding a polygonal graph having a face whose boundary is not a cyclic
graph.
I'm a bit suspicious here: "a polygonal graph having a face whose boundary is not a cyclic graph" — is this possible?
Pls enlighten me.
Best Answer
What if a vertex were trying as hard as it could to be a bridge?
The external face's boundary is not a cycle graph because the central vertex is repeated. We can make this difficulty far more evident...