In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.
Proved by Karl Menger in 1927, it characterizes the connectivity of a graph.
It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.
The edge-connectivity version of Menger's theorem is as follows:
Let G be a finite undirected graph and x and y two distinct vertices. Then the size of the minimum edge cut for x and y (the minimum number of edges whose removal disconnects x and y) is equal to the maximum number of pairwise edge-independent paths from x to y.
Extended to all pairs: a graph is k-edge-connected (it remains connected after removing fewer than k edges) if and only if every pair of vertices has k edge-disjoint paths in between.
The vertex-connectivity statement of Menger's theorem is as follows:
Let G be a finite undirected graph and x and y two nonadjacent vertices. Then the size of the minimum vertex cut for x and y (the minimum number of vertices, distinct from x and y, whose removal disconnects x and y) is equal to the maximum number of pairwise internally vertex-disjoint paths from x to y.
Extended to all pairs: a graph is k-vertex-connected (it has more than k vertices and it remains connected after removing fewer than k vertices) if and only if every pair of vertices has at least k internally vertex-disjoint paths in between.
All these statements (in both edge and vertex versions) remain true in directed graphs (when considering directed paths).
Most direct proofs consider a more general statement to allow proving it by induction. It is also convenient to use definitions that include some degenerate cases.
The following proof for undirected graphs works without change for directed graphs or multi-graphs, provided we take path to mean directed path.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
This course is an introduction to the theory of Riemann surfaces. Riemann surfaces naturally appear is mathematics in many different ways: as a result of analytic continuation, as quotients of complex
This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed. The edge-connectivity of a graph is the largest k for which the graph is k-edge-connected. Edge connectivity and the enumeration of k-edge-connected graphs was studied by Camille Jordan in 1869. Let be an arbitrary graph. If the subgraph is connected for all where , then G is said to be k-edge-connected. The edge connectivity of is the maximum value k such that G is k-edge-connected.
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.
In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected. A graph (other than a complete graph) has connectivity k if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them.
Covers the topology of Riemann surfaces and the concept of triangulation using finitely many triangles.
Explores the Ford-Fulkerson algorithm for solving the Max-Flow problem and its applications in network flow optimization.
Explores the Ford-Fulkerson method, max-flow, applications of max-flow, and the disjoint-set data structure.
We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...
Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...
Selective attention is a fundamental cognitive mechanism that allows our brain to preferentially process relevant sensory information, while filtering out distracting information. Attention is thought to flexibly gate the communication of irrelevant inform ...