number of totally different path between two nodes in graph theory - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T14:55:21Z http://mathoverflow.net/feeds/question/106736 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106736/number-of-totally-different-path-between-two-nodes-in-graph-theory number of totally different path between two nodes in graph theory hurtledown 2012-09-09T16:22:40Z 2012-09-09T18:26:48Z <p>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.</p> <p>how can I formally verify this? thank you</p> http://mathoverflow.net/questions/106736/number-of-totally-different-path-between-two-nodes-in-graph-theory/106744#106744 Answer by Igor Rivin for number of totally different path between two nodes in graph theory Igor Rivin 2012-09-09T18:26:48Z 2012-09-09T18:26:48Z <p>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 <a href="http://garryowen.csisdmz.ul.ie/~cs4115/resources/lect24.pdf" rel="nofollow">here</a>, though I am sure there are plenty of other places.</p>