Fact-checked by Grok 2 weeks ago

Menger's theorem

Menger's theorem is a fundamental result in graph theory that equates, for two non-adjacent vertices in an undirected graph, the size of the minimum vertex separator disconnecting them with the maximum number of internally vertex-disjoint paths connecting them, and analogously for edges with edge-disjoint paths.^[1]^[2] Named after the Austrian mathematician Karl Menger (1902–1985), the theorem was first published in 1927 as part of his work on general curve theory in topology and combinatorial geometry.^[3]^[4] There are two primary versions: the vertex version, which states that in a graph G, for non-adjacent vertices s and t, the minimum number of vertices whose removal separates s from t equals the maximum number of internally vertex-disjoint s-t paths; and the edge version, which states that the minimum number of edges whose removal separates s from t equals the maximum number of edge-disjoint s-t paths.^[1]^[2] These local connectivity statements extend to global forms: a graph with at least k+1 vertices is k-vertex-connected if and only if every pair of distinct vertices is joined by at least k internally vertex-disjoint paths, and similarly for k-edge-connectivity with edge-disjoint paths.^[1]^[2] The theorem's significance lies in its role as a min-max duality theorem, bridging path systems and separators, which underpins modern applications in network reliability, algorithm design, and flow theory.^[1]^[2] It provides the foundation for max-flow min-cut theorems in capacitated networks and has been generalized to directed graphs, matroids, and infinite graphs, influencing fields from computer science to operations research.^[2] Proofs often rely on augmenting path arguments or the max-flow min-cut theorem, highlighting its deep connections to other combinatorial principles.^[1]^[2]

History and overview

Historical background

Karl Menger, a mathematician at the University of Vienna, formulated the theorem in 1927 as part of his broader investigations into general curve theory within topology.^[5]^[6] His work at the time focused on characterizing connected compact topological spaces with specific neighborhood properties, where curves served as a bridge between continuous and discrete structures.^[7] The theorem appeared in Menger's paper "Zur allgemeinen Kurventheorie," published in German in the proceedings of Fundamenta Mathematicae.^[5] This publication emerged from the vibrant mathematical environment of the Vienna school, influenced by mentors like Hans Hahn, and addressed connectivity questions in abstract spaces that anticipated applications to graph structures.^[6] Menger's approach drew motivation from topological problems, including the embedding and separation of curves, which paralleled efforts to understand planarity and non-planar configurations in graphs.^[8] These ideas connected to contemporaneous work, such as Kazimierz Kuratowski's 1930 characterization of planar graphs, sharing roots in the topological analysis of embeddings and subdivisions.^[9] An early influence on Menger's thinking came from Dénes König's 1916 theorem on maximum matchings in bipartite graphs, which provided a minimax relation that Menger's result extended to vertex and edge connectivity in general graphs. König himself referenced Menger's theorem in his 1931 work, highlighting its combinatorial significance despite an incomplete proof attempt at the time.^[7] The theorem received its first notable English-language expositions and popularization in the 1950s amid the growing interest in combinatorial graph theory, with Gabriel Dirac providing accessible proofs and discussions that helped integrate it into the Anglo-American mathematical literature. Menger later reflected on its development in his 1981 reminiscences, crediting the theorem's spread to König's 1936 graph theory monograph and subsequent translations of related works.^[7]

Informal statement

Menger's theorem captures the essence of connectivity in graphs by equating the minimum number of vertices that must be removed to separate two non-adjacent vertices s and t with the maximum number of internally vertex-disjoint paths between them. In everyday terms, it measures how many independent routes exist between two points in a network and how many key junctions you'd need to block to cut off all routes. Similarly, for edges, the theorem links the minimum number of edges to remove for disconnection to the maximum number of edge-disjoint paths.^[2]^[10] This duality underscores the robustness of connections: more disjoint paths mean the network can withstand more failures before s and t become isolated. The theorem applies specifically to non-adjacent vertices to sidestep trivial direct connections, focusing instead on the graph's structural resilience.^[2] Consider a simple cycle graph C_4, forming a square with four vertices. Between two opposite (non-adjacent) vertices, exactly two internally vertex-disjoint paths exist—one along each side of the square—and removing those two intermediate vertices disconnects them, matching the theorem's equality.^[2] In a complete graph K_n, between any two vertices there are n-1 internally vertex-disjoint paths (the direct edge plus paths of length 2 through each of the other n-2 vertices), aligning with the graph's vertex connectivity of n-1.^[10] Introduced by Karl Menger in his 1927 work on curve theory, the theorem provides a foundational tool for assessing network reliability, such as in communication systems where disjoint paths represent alternative data routes.^[5]^[2]

Formal statement

Vertex-disjoint paths version

The vertex-disjoint paths version of Menger's theorem addresses connectivity in finite undirected graphs by relating the maximum number of internally vertex-disjoint paths between two vertices to the minimum size of a vertex separator disconnecting them.^[5] Formally, let G = (V, E) be a finite undirected graph, and let s, t \in V be non-adjacent vertices. An s-t vertex separator is a subset S \subseteq V \setminus \{s, t\} such that there is no path from s to t in G - S. The size of the minimum s-t vertex separator, denoted \kappa(s, t), equals the maximum number of internally vertex-disjoint s-t paths in G. An s-t path is internally vertex-disjoint from another if they share no vertices other than possibly s and t.^[5]^[11] This equivalence implies that if fewer than k vertices separate s from t, then at most k-1 internally vertex-disjoint s-t paths exist, and conversely, if the maximum number of such paths is at most k-1, then some k-1 vertices separate s from t. The theorem holds for simple graphs but extends naturally to multigraphs, where multiple edges between the same vertices do not affect vertex separations or internal disjointness.^[5]^[11] A key corollary concerns the global vertex connectivity \kappa(G) of G, defined as the minimum number of vertices whose removal disconnects G (or reduces it to a single vertex if G is complete). For non-complete graphs, \kappa(G) = \min\{\kappa(s, t) \mid s, t \in V, s \neq t, st \notin E\}, where the minimum is taken over all non-adjacent pairs. Thus, \kappa(G) equals the minimum over such pairs of the maximum number of internally vertex-disjoint paths between them.^[5]^[11] For example, consider the path graph P_4 with vertices s = v_1, v_2, v_3, t = v_4 and edges \{v_1v_2, v_2v_3, v_3v_4\}. The minimum s-t vertex separator has size 1 (e.g., \{v_2\} or \{v_3\}), and there is exactly one s-t path, which is internally vertex-disjoint from itself in the trivial sense, confirming the theorem.^[5]

Edge-disjoint paths version

In a finite undirected graph G, the maximum number of pairwise edge-disjoint paths between two distinct vertices s and t equals the size of a minimum s-t edge cut.^[12]^[13] An s-t edge cut is a set of edges whose removal disconnects s from t, and the minimum such set has cardinality denoted by the local edge-connectivity between s and t.^[13] Edge-disjoint paths are those that share no edges in common.^[14] This formulation differs from the vertex-disjoint paths version, which equates the maximum number of internally vertex-disjoint paths to the size of a minimum vertex separator.^[13] A key consequence is that the edge-connectivity \lambda(G) of G—the minimum size of an edge cut that disconnects G—equals the minimum, over all pairs of distinct vertices s and t in G, of the maximum number of edge-disjoint s-t paths.^[14] Moreover, \lambda(G) \leq \delta(G), where \delta(G) denotes the minimum degree in G, providing a bound that highlights the role of edge structure in connectivity.^[13] For illustration, consider the cycle graph C_4 on four vertices. Between any two non-adjacent vertices, the minimum edge cut has size 2 (removing the two edges incident to one vertex disconnects them), and there exist exactly two edge-disjoint paths connecting them along the cycle.^[13] This matches the theorem, as C_4 has edge-connectivity 2.^[14]

Relation to network flows

Equivalence with max-flow min-cut

Menger's theorem can be viewed as a special case of the max-flow min-cut theorem, which provides a foundational result in network flow theory. The max-flow min-cut theorem, independently proved by Ford and Fulkerson in 1956, states that in a flow network with a source s and sink t, the maximum value of an s-t flow equals the minimum capacity of an s-t cut.^[15] This theorem generalizes connectivity concepts to networks with arbitrary positive capacities on edges.^[15] The equivalence arises by constructing a flow network from the original graph where all relevant capacities are set to 1, transforming the problem of finding disjoint paths into one of computing maximum flow. In this setup, the maximum number of vertex-disjoint or edge-disjoint paths between two non-adjacent vertices equals the minimum number of vertices or edges whose removal disconnects them, aligning directly with Menger's theorem.^[16] This reduction demonstrates that Menger's result is isomorphic to the unit-capacity case of the max-flow min-cut theorem.^[17] Although Menger's theorem was established in 1927, predating the development of flow networks, its connection to the max-flow min-cut theorem was explicitly recognized in 1956 by Elias, Feinstein, and Shannon in their independent proof of the flow theorem. They noted the structural similarity, highlighting how Menger's combinatorial insight anticipates the flow duality.^[7] This linkage implies that Menger's theorem extends naturally to capacitated networks through the reduction, offering a broader framework for analyzing connectivity in weighted graphs without altering the core duality.^[16]

Modeling graphs as flow networks

To apply the max-flow min-cut theorem to Menger's theorem in finite undirected graphs, an original graph G = (V, E) with distinguished non-adjacent vertices s and t is transformed into a directed flow network, where capacities ensure that integer flows correspond to disjoint paths.^[18]^[19] For the edge-disjoint paths version, the construction directs each undirected edge \{u, v\} \in E into two directed edges (u, v) and (v, u), each with unit capacity 1; s serves as the source and t as the sink.^[19] The maximum flow in this network equals the maximum number of edge-disjoint s-t paths, as unit capacities limit flow along each edge to at most 1, and by the integrality theorem for flows, the flow decomposes into path flows of integer values.^[19] Any minimum cut corresponds to a minimum edge separator, whose capacity is the size of the smallest set of edges whose removal disconnects s from t.^[19] For the vertex-disjoint paths version, each vertex v \in V \setminus \{s, t\} is split into an in-vertex v_{\text{in}} and an out-vertex v_{\text{out}}, connected by a directed edge (v_{\text{in}}, v_{\text{out}}) of unit capacity 1; the original edge \{u, v\} becomes a directed edge (u_{\text{out}}, v_{\text{in}}) (and symmetrically (v_{\text{out}}, u_{\text{in}})) with infinite capacity.^[18]^[20] Here, s and t remain unsplit, with s as source and t as sink; the unit capacities on split edges enforce vertex disjointness by limiting flow through each intermediate vertex to at most 1, while infinite capacities on inter-vertex edges prevent bottlenecks there.^[18] The maximum flow equals the maximum number of internally vertex-disjoint s-t paths, and the minimum cut capacity matches the size of the minimum vertex separator.^[20] Consider a cycle graph C_4 with vertices s, a, t, b in order, where edges connect them sequentially and back to s. For the edge version, directing edges with unit capacities yields a maximum flow of 2, corresponding to the two edge-disjoint paths s \to a \to t and s \to b \to t.^[19] In the vertex version, splitting a and b with unit-capacity split edges and infinite-capacity connections results in a maximum flow of 2, matching the two vertex-disjoint paths and confirming the minimum vertex separator size of 2 (e.g., removing a and b).^[18]

Proofs

Proof via max-flow min-cut

To prove Menger's theorem via the max-flow min-cut theorem, begin by constructing the appropriate flow network from the undirected graph G = (V, E) with non-adjacent vertices s, t \in V, as detailed in the modeling graphs as flow networks section.^[21]^[20] For the edge-disjoint paths version, replace each undirected edge \{u, v\} \in E with two directed edges (u, v) and (v, u), each assigned capacity 1; all other capacities are infinite or zero as appropriate. By the max-flow min-cut theorem, the maximum flow value f from s to t equals the minimum cut capacity c.^[21] Since capacities are integers, the integral flow theorem guarantees an integer maximum flow, which decomposes into f unit-flow paths from s to t that are edge-disjoint in the original graph G (as each edge carries at most flow 1). Thus, f \leq \kappa'(s, t), the maximum number of edge-disjoint s-t paths.^[20] The minimum cut (S, T) with s \in S and t \in T has capacity c equal to the number of edges crossing from S to T, and these edges form an s-t edge separator in G. Every edge separator corresponds to such a cut (by taking S as the s-component after removal), so c = \lambda'(s, t), the minimum size of an s-t edge separator.^[21] Therefore, \kappa'(s, t) = f = c = \lambda'(s, t).^[20] For the vertex-disjoint paths version, split each non-s, t vertex v \in V \setminus \{s, t\} into v_{\text{in}} and v_{\text{out}}, adding a directed edge (v_{\text{in}}, v_{\text{out}}) with capacity 1; for each original edge \{u, v\} \in E, add directed edges (u_{\text{out}}, v_{\text{in}}) and (v_{\text{out}}, u_{\text{in}}) with infinite capacity (or sufficiently large to not constrain the flow). Treat s as source and t as sink without splitting. Again, the max-flow min-cut theorem yields maximum flow f equal to minimum cut capacity c.^[21] The integral flow decomposes into f unit-flow paths from s to t, each using distinct (v_{\text{in}}, v_{\text{out}}) edges for internal vertices, ensuring the paths are vertex-disjoint in G. Thus, f \leq \kappa(s, t), the maximum number of vertex-disjoint s-t paths.^[20] Any minimum cut must saturate finitely many capacity-1 edges (as infinite-capacity edges would yield infinite c), corresponding to a set of vertices whose removal separates s from t in G; every vertex separator induces such a cut, so c = \lambda(s, t), the minimum size of an s-t vertex separator.^[21] Hence, \kappa(s, t) = f = c = \lambda(s, t).^[20] This flow-based approach assumes no direct s-t edge, as adjacency would trivially provide one path and adjust separators accordingly; the construction handles this by excluding such edges or treating them separately without affecting the equality.^[21]

Combinatorial proof

The combinatorial proof of Menger's theorem relies on induction on the number of vertices in the graph, establishing the equivalence between the minimum size of an s-t separator and the maximum number of internally vertex-disjoint s-t paths for non-adjacent vertices s and t in a finite undirected graph G. This approach, originally due to Menger, avoids any reference to capacities or flows.^[13] One direction is immediate: if there exist k internally vertex-disjoint s-t paths, then any s-t separator must contain at least one internal vertex from each path (since s and t are non-adjacent and paths are internally disjoint), yielding a separator of size at least k.^[13] For the converse, proceed by induction on |V(G)|. For the base case, consider graphs with at most two vertices. If G consists solely of the isolated vertices s and t, there are no s-t paths and the empty set serves as a minimum separator, both of size 0. The statement holds vacuously for graphs with fewer than two vertices.^[13] Assume the theorem holds for all graphs with fewer than |V(G)| vertices. For the induction step, first address cases where G is disconnected. If G has a connected component C disjoint from {s, t}, then no s-t path intersects C, so s-t separators and paths in G are identical to those in G - C, which has fewer vertices; by the induction hypothesis, the equality holds in G - C and thus in G.^[13] Now suppose G is connected. Let κ be the size of a minimum s-t separator S. To show there are κ internally vertex-disjoint s-t paths, consider G - S, whose components do not contain both s and t. Let A be the component of G - S containing s (so t ∉ A). Since S is minimal, every vertex of S is adjacent to A (otherwise removing it would still separate). Let the vertices of S be v_1, ..., v_κ. By the induction hypothesis applied to the smaller graph induced by A ∪ {s} ∪ {v_i} for each i (or suitable subgraphs), there exist internally disjoint paths from s to each v_i within A ∪ S (treating the v_i as sinks). Similarly, construct internally disjoint paths from each v_i to t in the t-side components. Combining these yields κ internally vertex-disjoint s-t paths in G, each passing through a distinct v_i ∈ S. Special cases for bridges or multiple components are handled by reducing to the connected case via induction on subgraphs after edge removal.^[13] Dirac provided a simplification of this inductive argument in 1966, emphasizing clarity in the treatment of connected graphs and cutvertices for the vertex-disjoint case.^[22]^[23]

Generalizations and extensions

Directed graphs

Menger's theorem extends naturally to directed graphs (digraphs), where paths and cuts must respect the arc directions. In the vertex-disjoint paths version for digraphs, for distinct vertices s and t with no arc from s to t, the size of the minimum s-t vertex separator equals the maximum number of internally vertex-disjoint directed paths from s to t.^[14] An s-t vertex separator is a set of vertices excluding s and t whose removal eliminates all directed paths from s to t.^[24] Similarly, the edge-disjoint paths version states that, for any distinct vertices s and t, the size of the minimum s-t edge cut equals the maximum number of edge-disjoint directed paths from s to t.^[14] Here, an s-t edge cut is a set of arcs whose removal disconnects s from t in the directed sense.^[24] The condition of no direct arc from s to t in the vertex version mirrors the non-adjacency requirement in the undirected case, ensuring separators do not trivially include such an arc.^[14] A simple example illustrates the directed version: consider a directed cycle of length n \geq 3 with arcs oriented clockwise. For non-adjacent vertices s and t, there is exactly one directed path from s to t along the cycle, and the minimum s-t vertex separator has size 1 (removing any intermediate vertex disconnects them), matching the theorem.^[24] If the cycle were bidirected (arcs in both directions), the maximum number of internally vertex-disjoint paths would be 2, aligning with the minimum separator size of 2. Key differences from the undirected case arise because paths must follow arc directions, preventing cycles from providing multiple routes unless explicitly oriented to allow them. Connectivity in digraphs is typically measured by strong connectivity, where every pair of vertices has directed paths in both directions, and Menger's theorem characterizes the local strength of such connections between specific pairs.^[14] As a corollary, the theorem applies directly to special classes of digraphs, such as tournaments (complete digraphs with exactly one arc between each pair of vertices), where a k-strong tournament admits k internally disjoint directed paths from any x to any y.^[25] It also holds for directed acyclic graphs (DAGs), quantifying the number of disjoint topological paths between sources and sinks without cycles complicating the structure.^[24]

Infinite graphs

Menger's theorem extends to infinite graphs, where the notions of path families and separators are generalized using cardinalities to measure their sizes. In countable infinite graphs, the local version holds analogously to the finite case: for finite sets A and B, the maximum number of vertex-disjoint A-B paths equals the minimum size of a finite A-B separator. For global statements involving possibly infinite sets, the theorem equates the maximum cardinality of a family of vertex-disjoint A-B paths with the minimum cardinality of an A-B separating set.^[26] A landmark result in this area is the Aharoni–Berger theorem, which affirms Menger's theorem in its full generality for infinite digraphs. Specifically, for any sets A and B of vertices in a possibly infinite digraph, the maximum cardinality of a set of vertex-disjoint paths from A to B equals the minimum cardinality of a set of vertices separating A from B. This resolves a long-standing conjecture of Erdős from 1936, extending the theorem beyond countable cases to arbitrary infinities.^[26] Extending Menger's theorem to infinite graphs presents challenges, particularly in handling infinite paths that may not decompose neatly into disjoint families without advanced tools. For instance, in countable graphs, König's lemma plays a key role: it ensures that an infinite, locally finite tree contains an infinite path, facilitating the construction of disjoint paths in tree-like structures arising in proofs. In uncountable settings, issues of cardinality and non-constructive path existence further complicate direct adaptations of finite proofs. A illustrative example is the infinite ladder graph, formed by two disjoint infinite paths with corresponding vertices connected by edges (rungs). This graph exhibits infinite vertex-connectivity between its two ends, as there exist infinitely many vertex-disjoint paths linking sets near one end to sets near the other, matching the minimum infinite separator size. Proofs of these infinite versions typically invoke compactness principles to construct path systems. For example, the Aharoni–Berger proof employs Tychonoff's theorem on the product topology over partial path spaces, combined with stationary set methods and Fodor's lemma, to ensure the existence of maximal disjoint families without finite approximations failing at infinity. In countable cases, simpler inductive arguments using König's lemma suffice for path extensions.^[26] The infinite extension of Menger's theorem finds applications in the study of infinite graphs.

Recent extensions

In recent years, researchers have extended Menger's theorem to temporal graphs, where edges are labeled with specific times of availability. A key result establishes that Menger's theorem holds for vertex-disjoint temporal paths (as opposed to walks) in such graphs, meaning the maximum number of internally vertex-disjoint paths from a source to a sink equals the minimum size of a vertex cut separating them, provided the paths respect the time labels on edges.^[27] This extension, proven for both directed and undirected temporal graphs, addresses connectivity in time-varying networks by ensuring paths do not revisit vertices and adhere to non-decreasing time orders.^[27] Another significant development is an induced version of Menger's theorem, which requires the disjoint paths to form an induced subgraph, meaning no edges exist between vertices of different paths. This version holds for graphs of bounded maximum degree, where the theorem guarantees k pairwise non-adjacent paths between two sets of vertices if no smaller vertex cut separates them, with the bound depending on the degree parameter.^[28] The proof leverages structural properties of bounded-degree graphs to ensure the paths remain edge-free between them, providing a stronger separation guarantee useful in sparse network designs.^[28] Formal verification efforts have also advanced, with a complete mechanized proof of Menger's theorem for both directed and undirected finite graphs implemented in Isabelle/HOL, confirming the equivalence between the maximum number of disjoint paths and the minimum vertex cut.^[29] This formalization, which includes lemmas on graph connectivity and path systems, enables rigorous checking of the theorem's combinatorial core and supports extensions to more complex structures.^[29] Extensions to hypergraphs have explored connectivity preservation under reductions like splitting-off, where hyperedge operations maintain min-max relations akin to Menger's theorem for element-connectivity. In k-connected graphs, recent work has characterized the existence of short disjoint paths while preserving the theorem's disjointness.^[30] These extensions find applications in dynamic networks, such as optimizing temporal connectivity under cost constraints while ensuring Menger-like robustness against failures.^[30] They also aid constraint satisfaction problems by modeling path-based satisfiability in time-labeled or induced settings, where disjoint paths represent independent solutions to separation constraints.^[30]

References

[1]
[PDF] An Introduction to Combinatorics and Graph Theory - Whitman College
Proof of Menger's Theorem (5.7.7). Suppose first that between every two vertices v and w in G there are k internally disjoint paths. If G is not k-connected ...
[2]
[PDF] GRAPH THEORY WITH APPLICATIONS
Theorem 3.2 has a generalisation to k-connected. graphs, known as. Menger's theorem: a graph a with v >- k +1 is k-connected if and only if any two distinct ...
[3]
[PDF] Graph Theory - math kit
Nov 7, 2013 · Menger's theorem (1927): (Karl Menger Jan. 1902 - Oct. 1985). Let G be a graph, A, B ⊆ V (G). Min #vertices separating A and B = Max #vertex ...
[4]
[PDF] Three-Linkage on the Projected Plane - JEWLScholar@MTSU
Nov 6, 2024 · Karl Menger introduced his theorem in 1927 as part of his work in topology and combinatorial geometry. This was motivated by his evolving ...
[5]
Zur allgemeinen Kurventheorie - EuDML
Menger, Karl. "Zur allgemeinen Kurventheorie." Fundamenta Mathematicae 10.1 (1927): 96-115. <http://eudml.org/doc/211191>.
[6]
Karl Menger (1902 - 1985) - Biography - MacTutor
After Menger graduated from the Döblinger Gymnasium, he entered the University of Vienna in 1920 to study physics. He had not given up his idea of writing ...
[7]
[PDF] On the history of combinatorial optimization (till 1960) - CWI
Menger's theorem forms an important precursor of the max-flow min-cut theorem found in the 1950's by Ford and Fulkerson. The topologist Karl Menger published ...
[8]
Commentary on Menger's Work on Curve Theory and Topology
Sep 9, 2011 · Part of the attractiveness of the theory of curves to the young Karl Menger was its place in the mainstream of mathematics.
[9]
https://doi.org/10.4064/fm-15-1-271-283
[10]
[PDF] Graph Theory: Penn State Math 485 Lecture Notes
More Applications of the Max Flow / Min Cut Theorem. Theorem 7.39 (Menger's First Theorem). Let G be an (undirected) graph with V = {v1,...,vm}. Then the ...
[11]
[PDF] Math 530 Spring 2022, Lecture 27: Menger's theorems
Jan 1, 2022 · Let D = (V, A, ψ) be a multidigraph, and let s and t be two distinct vertices of D. Then, any s-t-cut is an s-t-arc-separator. Proof. Let B be ...Missing: theory | Show results with:theory
[12]
[PDF] Zur allgemeinen Kurventheorie
Zur allgemeinen Kurventheorie. Von. Karl Menger (Amsterdam). I. Über die Bedeutung der Ordnungszahl von Kurvenpunkten. II. Über umfassendate Kurven. III ...
[13]
[PDF] Reinhard Diestel - Graph Theory
The infinite version of Menger's theorem in Section 8.4 is a typical example: it offers algorithmic insights into connectivity problems in networks that are ...
[14]
[PDF] Section 9.3. Edge Connectivity
Feb 13, 2023 · We now shift our attention from vertex connectivity to edge connectivity. We give several definitions and some new versions of Menger's Theorem, ...Missing: formal | Show results with:formal
[15]
[PDF] maximal flow through a network - lr ford, jr. and dr fulkerson
THEOREM 1. (Minimal cut theorem). The maximal flow value obtainable in a network N is the minimum of v(D) taken over all disconnecting sets ...
[16]
[PDF] 1 Consequences of the max-flow min-cut theorem
Menger's Theorem equates the maximum number of such paths with the minimum number of edges or vertices that must be deleted from G in order to separate s from ...
[17]
[PDF] Fundamental Algorithms, Spring 2011 - Applications of Network Flows
Mar 31, 2011 · Menger proved his theorem before Maxflow-Mincut theorem! Maxflow-Mincut theorem is a generalization of Menger's theorem to capacitated ...Missing: equivalence | Show results with:equivalence
[18]
[PDF] Chapter 5 Flows in Networks
The next two sections contain the max-flow min-cut theorems along with some of their corollaries: Menger's theorem on connectivity, a result on lattices by ...
[19]
[PDF] network flows and the max-flow min-cut theorem - UChicago Math
The Max-Flow Min-Cut Theorem is a fundamental result within the field of network flows, but it can also be used to show some profound theorems in graph theory.
[20]
[PDF] Chapter 8 The Max-Flow Min-Cut Theorem - UCSD Math
Menger's Theorems (both vertex and edge versions). The Max-Flow Min-Cut Theorem. And some other results beyond this course. Prof. Tesler.
[21]
[PDF] Applications of Max Flow Min Cut - Brown Math
Theorem 0.3 (Menger) The maximum number of pairwise edge disjoint st-edges equals the minumum size of an edge cut. To prove this result, we introduce a modified ...
[22]
[PDF] Göring, Frank: A proof of Menger's theorem by contraction
Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927) 96–115. [8] J.S. Pym, A proof of Menger's theorem, Monatshefte Math. 73 (1969) 81–88. Received ...
[23]
[PDF] Menger's Theorem for directed graphs
Menger's Theorem for directed graphs. Given x, y ∈ V (D), a set S ⊆ V (D) \ {x, y} is an x, y-separator (or an x, y-cut) if D − S has no x, y- path ...
[24]
[PDF] Cycles in a tournament with pairwise zero, one or two given vertices ...
Aug 22, 2007 · By Menger's theorem, in a k-connected tournament, for distinct vertices x and y, there exist k internally disjoint paths going from x to y. An ...
[25]
PERCOLATION ON FINITE GRAPHS AND ISOPERIMETRIC ...
the fact that c = c(G) and Menger's theorem imply that there are at least ca n/3 pairwise edge-disjoint paths in G from A to B. As G has dn/2 edges, at ...
[26]
Menger's Theorem for Temporal Paths (Not Walks) - arXiv
In this paper we focus on various questions regarding connectivity (maximum number of disjoint paths) and robustness (minimum size of a cut) ...
[27]
On an Induced Version of Menger's Theorem
Nov 1, 2024 · Volume 31, Issue 4 (2024) /; Papers. On an Induced Version of Menger's Theorem. Kevin Hendrey; Sergey Norin; Raphael Steiner; Jérémie Turcotte.
[28]
Menger's Theorem - Archive of Formal Proofs
Feb 26, 2017 · We present a formalization of Menger's Theorem for directed and undirected graphs in Isabelle/HOL. This well-known result shows that if two ...Missing: statement | Show results with:statement
[29]
[PDF] On Approximate Min-Max Theorems for Graph Connectivity ...
An extension of Menger's theorem to hypergraphs states that these two definitions are actually equivalent. We shall discuss Menger's theorem. (and its many ...
[30]
Temporal Network Optimization Subject to Connectivity Constraints
Jul 5, 2018 · Then in Sect. 4 we present an analogue of Menger's theorem which we prove valid for arbitrary temporal graphs. We apply our Menger's analogue to ...