National University of Computer & Emerging Sciences
MT-3001 Graph Theory
Instructor: Miss Urooj
Connectivity and Flow
We have used connectivity in the context of problems. For example, we needed to know if a graph
was connected to determine if it has Eulerian circuit, Hamiltonian cycle, and we define trees as
minimally connected graphs; since the removal of any edge would disconnect the graph.
This chapter focuses on connectivity as its own topic, where we now consider how connected a
graph is, and not just whether it is connected or not.
One way to describe the clumping is in a connected graph, how many edges or vertices would need
to be removed before the graph is no longer connected, which is one way we measure connectivity.
Connectivity Measures:
When we define a graph to be connected, we refer to the existence of a way to move between any
two vertices in a graph, specifically as the existence of a path between any pair of vertices.
Note that any connected graph that is not complete has a cut-set, whereas 𝐾𝑛 does not have a cut-set.
Moreover, a graph can have many different cuts-sets of varying sizes.
For example: two different cut-sets are shown below in graph 𝐺1 .
1
k-Connected:
The distinction between k-connected and connectivity k is subtle yet important.
For example: if we say a graph is 3-connected, then we know there cannot be a cut-set of size 2 or
less in the graph; however, we only know that its connectivity is at least 3 (K(G) ≥ 3).
The example above demonstrates that more than one minimal cut-set can exist within a graph.
Moreover, any connected graph is 1-connected.
We are more interested in how large k can be before G fails to be k-connected.
2
k-Edge-Connected:
We now look at how many edges need to be removed before the graph is disconnected.
Recall that when we remove an edge e = xy from a graph, we are not removing the endpoints x and
y.
Clearly every connected graph has an edge-cut since removing all the edge from a graph will
result in just a collection of isolated vertices.
As with the vertex version, we are more concerned with the smallest size of an edge-cut.
3
Whitney's Theorem:
What do you think, is there any relationship between the vertex and edge connectivity
measures?
The examples above should demonstrate that these measures need not be equal, though they
can be.
How does the minimum degree of a graph play a role in these?
Notice how in both G2 and G3 above we found an edge-cut by removing both
edges incident to a specific vertex.
Remark:
Whitney’s Theorem provides an indication that high connectivity (or edge- connectivity)
requires a large minimum degree. But is the converse true?
Can a graph have a high minimum degree but low connectivity?
4
Connectivity and Paths:
Now we have some familiarity with connectivity, we turn to its relationship to paths within a
graph.
We will assume the graphs are connected, as otherwise, the results are trivial.
We begin by relating cut-vertices and bridges to paths.
It should be obvious that any edge along a cycle cannot be a bridge since its removal will
only break the cycle, not disconnect the graph.
More surprising is that all edges not on a cycle are in fact bridges.
5
Two disjoint paths are automatically internally disjoint and edge-disjoint, but two edge-disjoint
paths may or may not be internally disjoint.
Let G be a connected graph, and u, v be two non-adjacent vertices in G. A subset S of V − {u, v} is
said to separate u and v if G − S is disconnected and u and v are in different components of G−S.
A set I = {𝑄1 , 𝑄2 , ..., 𝑄𝑘 } of u−v paths (each Qi is a u−v path) in G is said to be internally-disjoint
if V (𝑄𝑖 ) ∩ V (𝑄𝑗 ) = {u, v} for all i, j with 1 ≤ i < j ≤ k.
Remarks:
Note that a cut-set may or may not be a separating set for a specific pair of vertices.
Consider graph 𝐺2 from page 169. We have already shown that {b, h} is a cut- set and {ab,
ah} is an edge-cut. If we want to separate b and c then we cannot use b in the separating set
and using the edges ab and ah will only isolate a, leaving b and c in the same component.
We can separate b and c using the vertices {f, h} and the edges {cd, cg, ch}.
Note that you cannot separate b and c with fewer or edges.
6
Menger’s Theorem:
The following theorems generalize the results relating a cut-vertex or bridge to paths in a graph.
Menger’s Theorem, and the resulting theorems, show the number of internally disjoint (or edge-
disjoint) paths directly corresponds to the connectivity (or edge-connectivity) of a graph.
Intuitive Idea:
For example: in 𝐺2 above we could separate b and c using two vertices and it should be easy to see
that b h c and b e f d c are internally disjoint b − c paths.
However, if we try to find more than two b − c paths then one of them cannot be internally disjoint
from the others.
Contracting an edge creates a smaller graph, both in terms of the number of vertices and edges but
keeps much of the structure of a graph intact.
In particular, contracting an edge cannot disconnect a graph.
Menger’s Theorem Statement:
7
Example:
Consider the graph G of Fig. 6.4.2(a) with two non-adjacent vertices u and v. It can be checked that
the minimum number of vertices separating u and v is 4, which is equal to the maximum number of
internally-disjoint u − v paths in G, as shown in Fig. 6.4.2(b).
An immediate result from Menger’s Theorem refers to the global condition of connectivity as
opposed to the separation of two specific vertices.
An edge version exists for the two previous theorems.
Remark:
When we are investigating graphs that are not trees, Menger’s Theroem (and the resulting theorems)
allow us to conduct similar analyses (about connectivity & paths).
Where the level to which a graph is connected is equal to the number of paths that would need to be
broken in order to separate two vertices.
