Edge-disjoint paths Created 2026-10-06 Updated 2026-10-07
Paths are edge-disjoint when no graph edge occurs in two of them. They may share internal vertices. If edge-disjoint client-to-server paths exist, fewer than failed links cannot destroy them all. For simultaneous link and node failures one instead needs internally vertex-disjoint paths, since one shared internal node could destroy several edge-disjoint paths at once.
A graph is a k-connected graph if it has at least vertices and deleting any set of fewer than vertices, together with their incident edges, leaves a connected graph.
The vertex connectivity is the largest such . Equivalently, for a graph with at least two vertices, it is the smallest number of vertices whose deletion either disconnects the graph or leaves a single vertex. The latter convention gives for a complete graph. A disconnected graph has vertex connectivity zero; one usually also sets .
For distinct nonadjacent vertices , the local connectivity isSuch a set is an – vertex separator. By Menger's theorem, local connectivity also equals the maximum number of internally vertex-disjoint paths from to . If no graph path exists already, the empty vertex separator gives zero.
The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices of a finite graph, the maximum number of internally vertex-disjoint paths from to equals the minimum size of an – vertex separator.
Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.
Here is the reduction, including the correspondence with vertex separators. Put . Perform vertex splitting on each vertex , replacing it by with a directed edge of flow network edge capacity one. Keep as the source and as the sink. For each original undirected edge , put directed edges from the output of to the input of and from the output of to the input of , each of flow network edge capacity ; an unsplit endpoint uses or itself.
A family of internally vertex-disjoint paths gives a feasible integral flow of value , by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.
Deleting a vertex separator corresponds to removing its split edges, of total flow network edge capacity . This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most . Thus the minimum cut capacity is no greater than the minimum vertex separator size.
For the reverse inequality, deleting all internal vertices separates , because they are nonadjacent. Hence a minimum cut has cut capacity at most and cannot contain a directed edge of flow network edge capacity . Its outgoing edges are therefore split edges. Let be the original vertices associated with them. Any – graph path avoiding would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.
Add two new vertices to , joining to every vertex of and to every vertex of , with no other new edges. The vertices are nonadjacent. Suppose has . Since is a k-connected graph, is a connected graph. Both and are nonempty because each original set has cardinality . Choose and ; a graph path between them in extends to an – graph path avoiding .
Consequently no fewer than vertices can form an – vertex separator. By Menger's theorem, there are at least internally vertex-disjoint paths from to . There cannot be more than , since has only neighbours.
Remove from these graph paths. The resulting graph paths in start at distinct vertices of , end at distinct vertices of , and are pairwise vertex-disjoint paths: any shared vertex would have been an internal vertex common to two of the original graph paths. Because there are exactly graph paths, they use every vertex of and as an endpoint. None can pass through another terminal internally, since that terminal already occurs as an endpoint of one of the vertex-disjoint paths. Thus there are vertex-disjoint paths from to , with some pairing of the endpoints. This is also an immediate application of the Set version of Menger theorem.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 37 3 c Solution Created 2026-10-03 Updated 2026-10-06
Name the outer pentagon vertices, in order from the client clockwise, . Name the upper inner vertex , the left inner vertex , and the lower-right inner vertex . The two remaining inner vertices are the labelled servers .
Four edge-disjoint server paths areEach uses different links, although some intermediary vertices are shared. Any three failed links therefore leave at least one path intact. The client has exactly four incident links; failing those four disconnects it. Thus the minimum link cut has size four, givingFor mixed failures use the three paths , and . Their internal vertices are disjoint, as are their links. One failed link or intermediary node can destroy at most one of these paths, so any two failures leave a path intact. Failing the three intermediary nodes disconnects both servers: has neighbors , and has neighbors . ThereforeThe two certificates distinguish edge-disjoint paths from internally vertex-disjoint paths, exactly the distinction needed between the two failure models.
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 2 17G i Solution Created 2026-09-24 Updated 2026-09-29
For nonadjacent vertices , the local connectivity is the minimum cardinality of an - vertex separator: a set such that and lie in different components of .
To prove the vertex form of the Menger theorem, replace every vertex by an arc of capacity one. Replace every undirected edge by directed arcs from to and conversely, each of capacity larger than ; leave unsplit. An integral - flow of value decomposes into paths, and the unit-capacity vertex arcs force the corresponding graph paths to be internally vertex-disjoint paths. Conversely, such paths give an integral flow of value .
Because and are nonadjacent, any finite minimum cut consists entirely of unit-capacity vertex arcs. These arcs correspond exactly to an - vertex separator of the same size. The max-flow min-cut theorem, whose augmenting-path proof also guarantees an integral maximum flow for integral capacities, therefore givesIn particular, contains the required set of paths.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 4 17H a Solution Created 2026-09-24 Updated 2026-09-25
The vertex form of Menger theorem states that if and are distinct nonadjacent vertices of a finite graph, then the maximum number of pairwise internally vertex-disjoint paths from to equals the minimum cardinality of an - vertex separator.
Topological minor 2026-10-14
A topological minor records a network pattern whose vertices remain individual junctions but whose edges may become longer routes. For finite simple graphs, means that contains a subgraph that is a graph subdivision of up to graph isomorphism. Equivalently, choose distinct branch vertices of a graph subdivision for and a graph path from to for every . These are internally vertex-disjoint paths, and no internal vertex of any is a branch vertex of a graph subdivision. Only endpoints corresponding to a shared target vertex may be shared.[ref]
The Basics (author-hosted chapter preview). §1.7, printed p. 18: subdivisions; printed p. 21: topological-minor embeddings
The graph subdivision example below replaces two edges of a triangle in a graph by routes of two and three edges while retaining its attached leaf of a graph. If the host graph also contains an extra edge , the same routes still witness a topological minor: delete when selecting the subgraph. An induced subgraph is not required. However, routes that merely connect the right pairs are insufficient: using a branch vertex of a graph subdivision as an intermediate junction, or making two routes share an internal vertex, can change the local network structure.
Every topological minor is a graph minor. In each branch path of a graph subdivision, contract all but one edge; the disjoint interiors let this shorten each route without merging distinct branch vertices of a graph subdivision. This recovers after deleting unused vertices and edges.[ref] The converse fails because an ordinary branch set of a graph minor can gather several junctions into one.
For the tree with vertices and edges , contracting produces a star graph : the branch sets of a graph minor are . Both have degree of a vertex three; each of the other four vertices is a leaf of a graph with degree of a vertex one. The new centre has four distinct graph neighbours ; its degree of a vertex is , in agreement with the edge contraction formula.
A graph minor can combine two junctions: contracting creates a star graph with a centre of degree of a vertex four
. Details. Yet is not a topological minor of . In a graph subdivision of , four branch paths of a graph subdivision must leave the centre through four different edges; sharing their first internal vertex would violate internal disjointness. Thus any host needs a vertex of degree of a vertex at least four, whereas . More generally, implies , where is the maximum degree of a graph. This bound concerns the host graph; extra unused edges may make its branch vertices of a graph subdivision have larger degrees of vertices than their target counterparts.
This distinction matters when a network's individual junctions have a limited number of connections: replacing a connection by a route preserves the number of routes meeting at each chosen junction, while contracting a connected region can combine connections from separate junctions. It also explains why a small nonplanar pattern can hide inside long routes. By Kuratowski's theorem, a finite simple graph is a planar graph exactly when it has neither the complete graph nor the complete bipartite graph as a topological minor. The obstruction is a graph subdivision inside the network, regardless of the number of intermediate vertices.
Vertex-disjoint paths 2026-10-25
Graph paths are vertex-disjoint if no vertex belongs to more than one of them, including their endpoints. In contrast, internally vertex-disjoint paths between common endpoints are allowed to share exactly those endpoints. The Set version of Menger theorem uses vertex-disjointness, while the two-terminal form uses internal vertex-disjointness.
