Can an articulation point have all edges as non-bridge

algorithmsgraph theory

The two endpoints of a bridge are articulation vertices unless they have a degree of 1. Will these articulation vertices form the complete set of articulation points of an undirected graph ?

Specifically, can there exist an articulation point such that every edge connecting it is not a bridge ?

Best Answer

Consider a graph on vertices $a,b,c,d,e$, where $a,b,c$ form a triangle, and $a,d,e$ also form a triangle. enter image description here

Then $a$ is an articulation point since removing it will disconnect the component $b,c$ from $d,e$. However, none of the edges incident to $a$ are bridges since they all lie on a cycle.

So you are correct, an articulation point can have no bridges incident to it.

Related Question