Is a non biconnected outerplanar graph just a tree?

60 Views Asked by At

I'm having a difficult time visualising it...

If we make it non biconnected, thus removing all vertices which give us alternative paths from 1 vertex to another, and with all vertices belonging to the outer face of the graph, wouldn't this be a tree?

2

There are 2 best solutions below

0
On

Here's a counterexample from the Wikipedia page of ”biconnected graph”.

Non biconnected outerplanar

0
On

No. The key thing is in order for a graph not to be biconnected, there only needs to be some pair of vertices where there is no path avoiding a certain intermediate vertex. (You seem to be thinking this needs to be true for every pair.)

So one way to be outerplanar but not biconnected (without being a tree) is to take a figure-eight type graph formed by identifying two cycles at a single vertex. It is not biconnected because removing that vertex disconnects the graph. Although any pair of vertices on the same cycle have two disjoint paths between them, for any two vertices on opposite sides the path needs to go though the central vertex.