Is there is a simple way to tell if a graph is 3-connected? In lecture, we use the definition that a graph is k connected iff it contains no proper separations of order < k $\therefore$ by this definition, a graph is 3-connected iff it contains no proper separations of order < 3. However using only this definition makes the process of determining if graphs are 3-connected rather arduous - and there is always the risk of missing a separation - so I was wondering if there were any other theorems/lemmas/corollaries/definitions which might make the process a bit quicker.
2026-03-26 19:00:44.1774551644
On
Is there is a simple way to tell if a graph is 3-connected
172 Views Asked by user911457 https://math.techqa.club/user/user911457/detail At
2
There are 2 best solutions below
0
On
An excellent description of a number of algorithms is given here. All of these are far more efficient than Whitney's algorithm.
Whitney's theorem is useful for vertex connectivity computations: A graph $G$ is $k$-connected if and only if for every pair of distinct vertices $a$, $b$ of $G$ there is a family of $k$ disjoint $a$, $b$-paths in $G$.
See Theorem 3.3.5. (Global Version of Menger's Theorem) in Reinhard Diestel's book Graph Theory.