MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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

If you want to calculate number of paths from one node to another ,let say from s to t.then you can follow the following approach.

To reach a node t from s , you need to calculate that how many ways are there to reach t from its adjacent vertices . means PathsTo(s,t)=sum(PathsTo(s,u)) , where u are adjacents vertices of t.

as we can see there is a subproblem optimality and overlapping subproblems, so we can use a DP approach to do this in Linear time.

We can do this by modifying our DFS algorithm.


declare an array A of size |V| , memset it to NULL array represent , number of ways to reach a node v from s.



 return 1;


      A[t]=sum(Paths(s,u)) for all adjacent u of t
      return A[t]

Time complexity is O(V+E) same as DFS.

share|cite|improve this answer

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.