# number of totally different path between two nodes in graph theory

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

-
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

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.

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

Psuedocode:

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

Paths(s,t):

if(s==t):

 return 1;


else:

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


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

-