From Egres Open
Jump to: navigation, search

Let G=(V,E) be an undirected graph, and [math]T \subseteq V[/math] a set of nodes that will be called terminal nodes. The nodes not in T are called Steiner nodes. The elements of G are the edges and the Steiner nodes. The graph G is k-element-connected if there are k element-disjoint paths between any two terminal nodes.

By Menger's theorem, the maximum number of element-disjoint paths between two terminal nodes equals the minimum number of elements needed to separate the two nodes.

The notion of k-element-connectivity can also be defined for directed graphs the same way.