2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

An excellent description of a number of algorithms is given here. All of these are far more efficient than Whitney's algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy