Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have an undirected, unweighted graph representing a network. I have a starting node and an end one. My 'network' is reliable if there is no node such that without that node s and t are not reachable i.e. no node is necessary and all nodes have at least one redundant path.

how can I formally verify this? thank you

share|improve this question
What do you mean by "formally verify"? What do you mean that "all nodes have at least one redundant path"? –  Igor Rivin Sep 9 '12 at 18:22
As stated by Igor, you want biconnectivity. A naive way to check this is to check, for each vertex $v$, that $G-v$ is connected. –  Andrew D. King Sep 10 '12 at 20:25

1 Answer 1

up vote 3 down vote accepted

If you mean that the network remains connected upon removing any one node, the magic words are "2-vertex-connected graph", or "biconnected graph". An algorithm for determining biconnectivity is described here, though I am sure there are plenty of other places.

share|improve this answer
Btw, the OP has stated (without proof) a special case of Menger's theorem. –  Felix Goldberg Sep 9 '12 at 20:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.