Polynomial time algorithm to find a 3-connected contracted graph

63 Views Asked by At

How can we describe a polynomial-time algorithm to find an edge $e$ in a graph $G$ such that $G/e$ is 3-connected. Given the fact that $G$ is 3-connected and $\lvert V(G) \rvert \geq 5$.

1

There are 1 best solutions below

0
On

There exist linear time algorithms for determining the 3-connected components of a 2-connected graph. If one of these applied to a graph results in only one component, that component is the graph itself, so it must be 3-connected.

The Wikipedia page on $k$-connected graphs says that there is a polynomial time algorithm for finding the connectivity of a graph using Menger's Theorem, but it gives no supporting references, so you'd need to do some digging elsewhere to verify it.

Either of these might be helpful in finding what you're looking for.