1.Previous
3.Next

of vertices in a graph that cannot be disconnected by the removal of few edges can be proven using the max-flow min-cut theorem from the theory of network flows.

Related concepts

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph is k-edge-connected then it is necessary that k <= ?(G), where ?(G) is the minimum degree of any vertex v ? V. Deleting all edges incident to a vertex v would disconnect v from the graph.

1.Previous
3.Next