Module 2

Connected graphs and

shortest paths

Contents
2.1

Walks, trails, paths, cycles . . . . . . . . . . . . . . . . . .

34

2.2

Connected graphs . . . . . . . . . . . . . . . . . . . . . . .

39

Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

Cut-vertices and cut-edges . . . . . . . . . . . . . . . . . . .

44

Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

2.3

Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . .

50

2.4

Weighted graphs and shortest paths . . . . . . . . . . . .

56

Weighted graphs . . . . . . . . . . . . . . . . . . . . . . . .

56

Dijkstras shortest path algorithm . . . . . . . . . . . . . .

58

Floyd-Warshall shortest path algorithm . . . . . . . . . . .

61

Exercises

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

66

34

Module 2. Connected graphs and shortest paths

Any network (communication or pipe line or transportation) consists of nodes

and physical links connecting certain pairs of nodes. One of the network problems
is to move objects (messages/liquids/vehicles) between two given nodes in shortest
possible time (or distance).
This real world problem can be easily modeled as a graph theoretic problem.
Figure 2.1 shows a communication network with five nodes, each of which is represented by a vertex. An edge represents a direct link. The integer along an edge
represents the time to send a message along that link.
v2
1

6
3

v1
8

v3
4

v5
2

v4
Figure 2.1: A communication network.
By examining all possible paths from v1 to v4 , we find that the shortest route
to send a message from v1 to v4 is along the path (v1 , v2 , v5 , v4 ) and it takes six units
of time. There exist good algorithms to find shortest paths which avoid brute force
method of examining all paths between two vertices.

2.1

Walks, trails, paths, cycles

The real world concept of moving objects between two nodes is captured in

the following terminology.

Definitions. Let G be a graph and let v0 , vt V (G).
A (v0 , vt )-walk is a finite alternating sequence

2.1. Walks, trails, paths, cycles

35

W (v0 , vt ) = (v0 , e1 , v1 , e2 , v2 , . . . , et , vt )
of vertices and edges such that ei is an edge incident with vertices vi1 and
vi , i = 1, 2, . . . , t.
v0 is called the origin and vt is called the terminus. Other vertices are called
the internal vertices. Note that v0 and vt can also be internal vertices.
The length of W is the number of edges it contains where an edge is counted
as many times as it occurs.
W is called a closed walk, if v0 = vt .
Remarks.
In a walk, vertices and edges may appear any number of times.
If there exists a (v0 , vt )-walk, then there exists a (vt , v0 )-walk.
If G is a simple graph, W is denoted as a sequence of vertices (v0 , v1 , . . . , vt )
with the understanding that (vi , vi+1 ) is an edge, for i = 0, 1, . . . , t 1.
Definitions.
A (v0 , vt )-walk is called a (v0 , vt )-trail, if no edge is repeated (but vertices may
get repeated). It is called a closed trail if v0 = vt .
A (v0 , vt )-walk is called a (v0 , vt )-path, if no vertex is repeated (and therefore
no edge is repeated).
By definition, every path is a trail and every trail is a walk. However, a walk
need not be a trail and a trail need not be a path.
A closed walk W (v0 , vt ) is called a cycle, if all its vertices are distinct except
that v0 = vt .
A cycle with k vertices is called a k-cycle and it is denoted by Ck . A C3 is also a
K3 and it is referred to as a triangle. A 1-cycle is a loop and a 2-cycle consists
of two multiple edges.

36

Module 2. Connected graphs and shortest paths

Any subsequence W 1 (vi , vj ) = (vi , ei+1 , vi+1 , . . . , vj ) of W is called a subwalk

of W. We illustrate these concepts by taking a graph.

v2
e1
v1

e4

e2

e6

v3
e5

e3

v5
e7

v4
Figure 2.2: A graph G.
Define:
(1) W1 (v1 , v5 ) = (v1 , e1 , v2 , e4 , v3 , e2 , v1 , e3 , v4 , e5 , v3 , e4 , v2 , e6 , v5 ).
(2) W2 (v1 , v5 ) = (v1 , e1 , v2 , e4 , v3 , e2 , v1 , e3 , v4 , e7 , v5 ).
(3) W3 (v1 , v5 ) = (v1 , e1 , v2 , e4 , v3 , e5 , v4 , e7 , v5 ).
(4) W4 (v1 , v1 ) = (v1 , e1 , v2 , e4 , v3 , e2 , v1 , e3 , v4 , e5 , v3 , e2 , v1 ).
(5) W5 (v1 , v1 ) = (v1 , e1 , v2 , e4 , v3 , e5 , v4 , e3 , v1 ).
Here, W1 is a (v1 , v5 )-walk of length 7. It is not a trail. W2 is a trail of length
5 but it is not a path. W3 is a path of length 4. W4 is a closed walk of length 6 but
it is not a cycle. W5 is a cycle of length 4. As per our convention, W5 is also denoted
by (v1 , v2 , v3 , v4 , v1 ).
Theorem 2.1. Every (v0 , vt )-walk W contains a (v0 , vt )-path.
Proof. Among all (v0 , vt )-subwalks of W , let P (v0 , vt ) be a subwalk of W which has
minimum length. We claim that P is a path. Otherwise, there exist i and j (say
i < j) such that vi = vj . That is,
P (v0 , vt ) = (v0 , . . . , vi , ei+1 , vi+1 , . . . , vj (= vi ), ej+1 , vj+1 , . . . , vt ).

37

2.1. Walks, trails, paths, cycles

By deleting the subsequence (ei+1 , vi+1 , . . . , vj ), we obtain a (v0 , vt )-subwalk of W

which has lesser length, which is a contradiction to the minimality of P . So, P (v0 , vt )
is a path.
Theorem 2.2. If G is simple and (G) 2, then there exists a cycle of length of at
least (G) + 1 in G.
Proof. Let P be a path of maximum length in G. Let P = (v1 , v2 , . . . , vt ). If v is
a vertex adjacent with v1 , then v {v2 , v3 , . . . , vt }; else (v, v1 , v2 , . . . , vt ) is a path
of greater length, which is a contradiction to the maximality of P . So, N (v1 )
{v2 , v3 , . . . , vt }. Let vk be the last vertex in P to which v1 is adjacent; see Figure
2.3. Then the subpath Q = (v1 , v2 , . . . , vk ) contains at least deg(v1 ) + 1 (G) + 1
v1

v2

vk

vt

Figure 2.3: A maximum path P(v1 , vt ) and the resultant cycle.

vertices, and so (v1 , v2 , . . . , vk , v1 ) is a cycle of length (G) + 1.
Theorem 2.3. Every graph G with m(G) n(G) contains a cycle.
Proof. If G contains a loop (= a 1-cycle) or a multiple edge (= a 2-cycle) we are
through. So, we prove the theorem for simple graphs. This we do by induction on n.
If n 3, then there is only one graph with m n, namely C3 . So we proceed to the
induction step. If (G) 2, then G contains a cycle by Theorem 2.2. Next assume
that (G) 1, and let v be a vertex of degree 1 in G. Then G v is a graph with
m(G v) n(G v). Therefore, by induction hypothesis, G v contains a cycle.
Hence G too contains a cycle.
Definitions. If G contains a cycle, then the following are defined.

38

Module 2. Connected graphs and shortest paths

The length of a shortest cycle in G is called its girth.
The length of a longest cycle in G is called its circumference.
If G is acyclic, then girth and circumference are defined to be .
Graph
Girth
Circumference

Pn

Cn
n
n

Kn
3
n

c
Km
+ Knc
4
2 min{m, n}

Qn
4
2n

P
5
9

Table 2.1: Girths and Circumferences; m, n 3 and P is the Petersen graph.

Corollary. If G is simple and (G) 2, then circumf erence(G) (G) + 1.
Proof. A consequence of Theorem 2.2
Theorem 2.4. If G is a simple graph on least six vertices, then either
(i) G contains at least three vertices which are mutually adjacent, or
(ii) G contains at least three vertices whcih are mutually non-adjacent.
Proof. Let v be a vertex. Since n 6,
either (a) there are at least three vertices, say v1 , v2 , v3 , which are adjacent to v, or
(b) there are at least three vertices, say u1 , u2 , u3 which are non-adjacent to v.
Suppose (a) holds (see Figure 2.4):
If there are two vertices in {v1 , v2 , v3 } which are adjacent, say v1 , v2 , then
v, v1 , v2 are three mutually adjacent vertices. On the other hand, if no two vertices of
{v1 , v2 , v3 } are adjacent, then v1 , v2 , v3 are three mutually non-adjacent vertices. So,
(i) or (ii) holds as claimed in the theorem.

Suppose (b) holds:

If there are two vertices in {u1 , u2 , u3 }, which are non-adjacent say u1 , u2 ,
then v, u1 , u2 are three mutually non-adjacent vertices. On the other hand, if any

39

2.2. Connected graphs

v1 v2 v3

u1 u2 u3

Figure 2.4: Adjacency of v.

two vertices in {u1 , u2 , u3 } are adjacent, then u1 , u2 , u3 are three mutually adjacent
vertices. So, (i) or (ii) holds.
The above theorem can be reformulated as follows:
Theorem 2.5. If G is a simple graph on at least six vertices, then either K3 G or
K3 Gc .

Remarks.
The assumption n 6 made in Theorem 2.4 is necessary. For example, C5 is a
graph on five vertices which satisfies neither (i) nor (ii).
Which of the problems stated at the beginning of this course is now solved?

2.2

Connected graphs
Clearly, we can move objects between two nodes if they are connected.

Definitions.
In a graph G, two vertices u and v are said to be connected, if there exists a
(u, v)-path.
G is said to be a connected graph if any two vertices are connected; else, G
is said to be a disconnected graph.
A maximal connected subgraph H of a graph G is called a component of G;
maximal in the sense that if H1 is a connected subgraph of G such that H H1 ,
then H = H1 .

40

Module 2. Connected graphs and shortest paths

The number of components in a graph G is denoted by c(G). So, c(G) = 1 if
and only if G is connected.
9

Figure 2.5: A graph G with four components.

9
5

(a) H1

(b) H2

Figure 2.6: Two subgraphs of G which are not its components; they are connected
subgraphs but not maximal connected subgraphs.
Theorem 2.6. For any graph G, m(G) n(G) c(G).
Proof. We prove the theorem by induction on n.
Basic step: If n = 1, the result is obvious.
Induction step: If (G) 2, then m(G) =

1
2


d(v)
21 (2n(G)) = n(G) >
vV (G)

P

n(G) c(G). If (G) = 0, let v be a vertex of degree 0. Then

m(G) = m(G v)
n(G v) c(G v), by induction hypothesis,
= (n(G) 1) + (c(G) 1)
= n(G) c(G).

2.2. Connected graphs

41

Next assume that (G) = 1, and let v be a vertex of degree 1. Then c(G v) = c(G).
So,
m(G) = m(G v) + 1
n(G v) c(G v) + 1, by induction hypothesis,
= (n(G) 1) c(G v) + 1
= n(G) c(G).
Corollary. For any connected graph G, m(G) n(G)1.

Theorem 2.7. Every graph with m n 1 is either connected or contains a cycle.

Proof. It is enough if we prove the theorem for simple graphs. Assume the contrary
and let G be a simple graph with m n 1 which is neither connected nor contains
a cycle. Let G1 , G2 , . . . , Gt be its component where t 2. Let Gi have ni vertices
and mi edges, i = 1, 2, . . . , t. Since Gi is acyclic, using Theorem 2.3, we deduce that
mi ni 1. So,
m = m1 + m2 + + mt
(n1 1) + (n2 1) + (nt 1)
=nt
n 2.
This is a contradiction to our assumption that m n 1.
Theorem 2.8. A connected simple graph G contains a cycle if and only if m n.
Proof. If m n, then G contains a cycle by Theorem 2.3. The reverse implication
can be proved by induction on n by following the proof of Theorem 2.7.

42

Module 2. Connected graphs and shortest paths

The above theorem characterizes the graphs with a cycle. However, it is a

difficult open problem to find sufficient conditions (or necessary conditions) for the
existence of a cycle Ck of specified length k. The following theorem gives a sufficient
condition for a simple graph to contain a C3 .
Theorem 2.9. Every simple graph with m >

n2
4

contains a cycle of length 3(=

triangle).

Proof. We prove that if G is a simple graph which has no triangles, then m

n2
.
4

This we do by induction n.
Case 1: n is even.
If n = 2, then the inequality is obvious. So, we proceed to the induction step
assuming that G has n + 2 vertices and that the theorem holds for all graphs on n
vertices. There exists an edge (u, v) in G; else, m = 0. We partition E(G) into three
parts as follows:
(1) E(G) = E(G {u, v}) {e E(G) : e has one end vertex in {u, v} and other
end vertex in G {u, v}} {(u, v)}.
Since G{u, v} has no triangles, m(G{u, v})

n2
,
4

by induction hypothesis.

No vertex in G {u, v} is adjacent to both the vertices u and v, since G has no

triangles. So
|{e E(G) : e has one end vertex in {u, v} and other end vertex in G {u, v}}|
n(G {u, v}) = n.
Hence, m(G) m(G {u, v}) + n + 1

n2
4

+n+1=

Case 2: n is odd. Proof is exactly as above.

(n+2)2
.
4

2.2. Connected graphs

43

Distance
The concept of distance occurs in every branch of mathematics; graph theory

is no exception.
Definitions. Let G be a graph and u, v V (G).
The distance dG (u, v) or d(u, v) between u and v is defined as follows:

length of a shortest (u, v) path, if u and v are connected,

dG (u, v) =
,
if u and v are not connected.
The diameter of G, diam(G), is defined by

max{d(u, v) : u, v V (G)}, if G is connected,

diam(G) =
,
if G is disconnected.
If G is connected, then the function d : V (G) V (G) R is a metric on
V (G). Formally, we state this fact as a theorem. Its proof is easy and hence it is left
as an exercise.
Theorem 2.10. If G is a connected graph, then (V (G), d) is a metric space. That
is:
(i) d(u, v) 0, for every u, v V (G).
(ii) d(u, v) = 0 iff u = v.
(iii) d(u, v) = d(v, u), for every u, v V (G).
(iv) d(u, v) d(u, w) + d(w, v), for every u, v, w V (G).

Theorem 2.11. Let A = [aij ] be the adjacency matrix of a simple graph G. Then the
(i,j) th entry [Ap ]ij in Ap is the number of walks of length p from vi to vj .
Proof. We prove the theorem by induction on p. If p = 1, then Ap is A and the
result is obvious. Suppose that the result is true for p = r and let p = r + 1. We

44

Module 2. Connected graphs and shortest paths

have,
r+1

[A

n
X
]ij =
[Ar ]ik akj .
k=1

Now
[Ar ]ik akj

[Ar ] ,
ik
=
0

if akj = 1, that is, if vk and vj are adjacent.

if akj = 0, that is, if vk and vj are not adjacent.

By induction, [Ar ]ik is the number of walks of length r connecting vi and vk . Each of
these walks is extendable to a walk of length r + 1 connecting vi and vj iff vk and vj
are adjacent, that is, iff akj = 1. So, by the above equations, [Ar+1 ]ij is the number
of walks of length r + 1 connecting vi and vj .
Theorem 2.12. If G is a connected simple graph, then the distance between vi and
vj is the smallest integer p( 0) such that [Ap ]ij 6= 0.
Proof. By the minimality of p, [Ar ]ij = 0, for every r, 0 r p 1. So, by Theorem
2.11, there is no walk of length p 1 connecting vi and vj ; hence, d(vi , vj ) p.
Since [Ap ]ij 6= 0, there does exist a walk, say W (vi , vj ), from vi to vj . Since, [Ar ]ij =
0, for all r, 0 r p 1, W (vi , vj ) is a walk of minimum length and hence it is a
path. So, d(vi , vj ) p. Combining the two inequalities we get d(vi , vj ) = p.

Cut-vertices and cut-edges

The following two concepts make precise the notions of faulty nodes and faulty

links. At the outset, observe that the number of components in G v may increase
or decrease or remain the same, when compared to the number of components in G.
In fact, c(G v) < c(G) iff deg(v) = 0.
Let G be a graph, v be a vertex and e be an edge.
Definition. v is said to be a cut-vertex if c(G v) > c(G).

45

2.2. Connected graphs

Remarks.
If G is connected, then v is a cut-vertex if G v is disconnected.
v is a cut-vertex of G if and only if v is a cut-vertex of a component of G.

(a) G1

(b) G2

(c) G3

Figure 2.7: G1 contains exactly one cut-vertex, G2 contains three cut-vertices and G3
contains no cut-vertices.
Definition. e is said to be a cut-edge of G if c(G e) > c(G).
Remarks.
If e(u, v) is a cut-edge of G, then u and v are in two different components of
G e. Moreover, c(G e) = c(G) + 1.
The two remarks made above with respect to a cut-vertex hold good for a
cut-edge also.

(a) G1

(b) G2

(c) G3

(d) G4

Figure 2.8: Every edge in G1 is a cut-edge, G2 contains exactly one cut-edge and two
cut-vertices, G3 contains a cut-vertex but contains no cut-edge, G4 contains neither
a cut-vertex nor a cut edge.
Theorem 2.13. A vertex v of a connected graph is a cut-vertex if and only if there
exist vertices x and y (6= v) such that every (x, y)-path contains v.

46

Module 2. Connected graphs and shortest paths

Proof. (1) Suppose v is a cut-vertex. G v is disconnected so it contains at least

two components, say C and D. Let x V (C) and y V (D). Since there is no
(x, y)-path in G v, it follows that every (x, y)-path in G contains v.
(2) Suppose there exist x and y (6= v) such that every (x, y)-path contains v. It
follows that there is no (x, y)-path in G v. Hence G v is disconnected, that is v
is a cut-vertex.
Theorem 2.14. Let G be a connected graph with at least three vertices. If e(u, v) is
a cut-edge in G, then either u or v is a cut-vertex.
Proof. In G e, there exist two components C and D such that u V (C) and
v V (D). Since n 3, either n(C) 2 or n(D) 2, say n(C) 2. Then u is a
cut-vertex of G.
Remarks.
By the above theorem, it follows that if G is connected, n(G) 3 and G has
a cut-edge, then G has a cut-vertex. However, the converse is false: The graph
G3 shown in Figure. 2.8 contains a cut-vertex but contains no cut-edges.
If e(u, v) is a cut-edge, then it is not necessary that both u and v are cutvertices; if d(u) 2 and d(v) 2, then both u and v are cut-vertices.
Theorem 2.15. An edge e(u, v) is not a cut-edge of G if and only if e belongs to a
cycle in G.
Proof. (1) Suppose e is not a cut-edge.
So, G e is connected, and u, v are in the same components of G e. So, there
exists a path P (u, v) in G e. But then, (P (u, v), v, u) is a cycle in G containing e.
(2) Suppose e belongs to cycle C in G.

47

2.2. Connected graphs

So, C e is a (u, v)-path in G e. Hence, u and v are in the same components

of G e, that is G e is connected. Therefore, e is not a cut-edge.
Theorem 2.16. Every connected graph G with n 2, contains at least 2 vertices
which are not cut-vertices.
Proof. Let P be a path of maximum length in G; let P = P (x, y). Our claim is that
neither x nor y is a cut-vertex of G. On the contrary, suppose x is a cut-vertex and
consider G x; see Figure 2.9. It contains at least 2 components say C and D where
y D. Let v be any vertex in C. Then every (v, y)-path in G contains x.

v
C

P1

P2

x
Figure 2.9: Existence of two paths P1 and P2 in G.

But then Q = (P1 (v, x), P2 (x, y)) is a path of length greater than the length
of P , a contradiction to the maximality of P .

Blocks

Definition.

A maximal connected subgraph B of a graph G that has a no cut-

vertex of its own is called a block of G; maximal in the sense that if H is a connected
subgraph of G that has no cut-vertex and H B, then H = B; see Figure 2.10.
If G has no cut-vertices, then G is called a block.
Remarks.

48

Module 2. Connected graphs and shortest paths

2
1

5
4

9
1

10

(a) G

5
4

10

(b) Blocks of G.

Figure 2.10: A graph G and its five blocks.

A block of a graph does not have a cut-vertex of its own. However, it may
contain cut-vertices of the whole graph. In example 2.10a, the edge joining 4
and 6 is a block and both the end points are cut-vertices of the whole graph.
By definition, G itself is a block if it is connected and it has no cut-vertex.
Two blocks in a graph share at most one vertex; else, the two blocks together
form a block, thus contradicting the maximality of blocks.
If two distinct blocks of G share a vertex v, then v is a cut-vertex of G.
Any two distinct blocks are edge disjoint; so the edge sets of blocks partition
the edge set of G.
To establish a property P of a graph G, often it is enough to establish P for
each of its blocks, and thereby simplify the proofs.
Definition. Two paths P (x, y) and Q(x, y) are said to be internally disjoint if
they have no internal vertex common.
The following result is a special case of a theorem proved by Menger (1932).
Theorem 2.17. Let G be a graph with n(G) 3. Then G is a block if and only
if given any two vertices x and y of G, there exist at least two internally disjoint
(x, y)-paths in G.
Proof. (1) Given any two vertices x, y of G, there exist at least two internally disjoint
(x, y)-paths G is a block.

49

2.2. Connected graphs

By the hypothesis, G is connected. So, we have to only show that G has no

cut-vertices. On the contrary, suppose v is a cut-vertex of G. Then by Theorem 2.13,
there exist vertices x, y such that every (x, y)-path passes through v. This implies
that there do not exist two internally disjoint (x, y)-paths, which is a contradiction
to the hypothesis.
(2) G is a block Given any two vertices x, y of G, there exist at least two internally
disjoint (x, y)-paths.
We prove the implication by induction on the distance d(x, y).
Basic step: d(x, y) = 1. Let e be an edge joining x and y. Then G e is connected;
else, x or y is a cut-vertex which is a contradiction, since G is a block. Hence, there
exists a path P (x, y) in Ge. But then (x, e, y) and P (x, y) are two internally disjoint
(x, y)-paths.
Induction step: d(x, y) > 1. Let P (x, y) be a shortest (x, y)-path; so length of
P = d(x, y). Let w be a vertex that precedes y in P . So, d(x, w) = d(x, y) 1.
Hence, by induction hypothesis, there exist two internally disjoint (x, w)-paths, say
Q(x, w) and R(x, w); see Figure 2.11.

S
Q
z
x

Figure 2.11: Construction of two internally disjoint (x, y)-paths in G.

50

Module 2. Connected graphs and shortest paths

Since G is a block, w is not a cut-vertex. So, there exists a path S(x, y) in

G w. Let z be the last vertex in S(x, y) that lies in V (Q) V (R). For definiteness,
let z V (Q). Then (Q(x, z), S(z, y)) and (R(x, w), w, y) are two internally disjoint
(x, y)-paths.
A reformulation of the above theorem yields an alternative characterization of
a block.
Corollary. A graph G with at least three vertices is a block if and only if given any
two vertices x and y, there exists a cycle containing x and y.

2.3

Connectivity
Consider the graphs shown in Figure 2.12 representing communication or

transportation networks. They are successively more robust. k-vertex-connectivity

and k-edge-connectivity are two basic parameters that measure the robustness of a
graph/network.

(a) G1

(b) G2

(c) G3

(d) G4

(e) G5

Figure 2.12: Successively more robust graphs.

Definitions (k-vertex-connectivity).
A vertex subset W V (G) is called a vertex-cut if G W is disconnected or
G W is a single vertex graph.
The integer
k0 (G) = min{|W | : W V (G), W is a vertex-cut}.

2.3. Connectivity

51

is called the vertex-connectivity of G. That is, k0 (G) is the minimum number

of vertices whose deletion disconnects G or results in a graph with a single
vertex.
Any vertex-cut K V (G) such that |K| = k0 (G) is called a minimum vertexcut of G.
A graph G is said to be p-vertex-connected, if k0 (G) p.
Remarks.

k0 (G) = 0 if and only if G is disconnected or G is a single vertex graph.

k0 (G) = 1 if and only if G is connected and it has a cut-vertex.
k0 (G) 2 if and only if G is a block.
k0 (G) = n(G) 1 if and only if G Kn .
A graph G may have many minimum vertex-cuts but k0 (G) is unique.
If G is p-vertex-connected, then it is t-vertex-connected for every t, 1 t p.
Thus a 3-connected graph is also a 2-connected graph and a connected graph.

Definitions (k-edge-connectivity).
An edge subset F E(G) is called an edge-cut if G F is disconnected or
G F is a single vertex graph.
The integer
k1 (G) = min{|F | : F E(G) and F is an edge cut}
is called the edge-connectivity of G. That is, k1 (G) is the minimum number
of edges whose deletion disconnects G or results in a single vertex graph.
Any edge-cut F E(G) such that |F | = k1 (G) is called a minimum edge-cut.
A graph G is said to be s-edge-connected if k1 (G) s.
Remarks.

52

Module 2. Connected graphs and shortest paths

k1 (G) = 0 if and only if G is disconnected or G is a single vertex graph.
k1 (G) = 1 if and only if G is connected and G has a cut-edge.
k1 (G) (G); this follows since by deleting all the edges incident with a vertex
of minimum degree, we disconnect the graph.
A graph G may have many minimum edge-cuts but k1 (G) is unique.
If G is s-edge-connected, then it is t-edge-connected, for every t, 1 t s.
If F is a minimum edge-cut, then G F contains exactly two components A
and B such that [V (A), V (B)] = F .
Table 2.2 shows the above two parameters for the graphs shown in Figure 2.12,

some standard graphs (n 3) and the Petersen graph P .

k0
k1

G1
0
0

G2
1
1

G3
1
2

G4
2
3

G5
4
4

Kn
n1
n1

Pn
1
1

Cn
2
2

P
3
3

Table 2.2: Vertex and edge connectivity of graphs

Theorem 2.18. For any graph G on at least two vertices, k0 (G) k1 (G) (G).
Proof. We have already remarked above that k1 (G) (G). Below we prove that
k0 (G) k1 (G). If G is disconnected or G is a single vertex graph, then k0 (G) =
0 = k1 (G), (G) 0. So, next assume that G is connected. If n(G) = 2, then
k0 (G) = 1, k1 (G) = number of edges joining the two vertices, and (G) number of
edges joining the two vertices . Therefore the result follows. Next assume that G is
connected and n(G) 3.
Case 1: G is simple.
Let k1 (G) = and let F = {e1 (u1 , v1 ), . . . , e (u , v )} be a minimum edge-cut
where ui and vj need not be distinct. Let H = G ({u1 , u2 , . . . , u1 } {u , v }).
Then e is a cut-edge of H. So, u or v is a cut-vertex of H; say u . But then

53

2.3. Connectivity
{u1 , . . . , u1 , u } is a vertex-cut of G. Therefore, k0 (G) = k1 (G).
Case 2: G is any graph.

Let H be an underlying simple spanning subgraph of G. Then k0 (H) = k0 (G)

and k1 (H) k1 (G). We deduce that k0 (G) = k0 (H) k1 (H) k1 (G).
Remark. The inequalities shown in Theorem 2.18 are best possible in the following
sense. Given any three integers r, s, t such that 0 r s t, there exists a simple
graph G with k0 (G) = r, k1 (G) = s, (G) = t. (We leave it as an exercise to construct
such a graph G. You can take a hint from the two graphs shown in Figure 2.13.)

(a) G1

(b) G2

Figure 2.13: k0 (G1 ) = 1, k1 (G1 ) = 2, (G1 ) = 3; k0 (G2 ) = 3, k1 (G2 ) = 4, (G2 ) = 4.

Two central theorems on connectivity are due to K. Menger (1932).

Theorem 2.19. A graph G is k-vertex connected (1 k n 1) if and only if given
any two distinct vertices u and v, there exist k internally disjoint (u, v)-paths (that
is, no two of the paths have an internal vertex common).
Theorem 2.20. A graph G is k-edge connected if and only if given any two distinct
vertices u and v, there exists k edge-disjoint (u, v)-paths (that is, no two paths have
an edge common).
There are many sufficient conditions for a graph to be k-vertex-connected or
k-edge-connected. We state and prove two results, and a few are included in the
exercise list.
Theorem 2.21. Let 1 k n. If degG (v)
k-vertex-connected.

 n+k2 
, for every vertex v, then G is
2

54

Module 2. Connected graphs and shortest paths

Proof. Let W V (G) be a k-vertex-cut. Then G W contains at least two components and so it has a component D such that d := |V (D)|

nk
.
2

Let x be a vertex

in D; see Figure 2.14.

x
D

GW

W
Figure 2.14: Estimate for degG (x).

Then x can be adjacent to at most d 1 vertices in G W and k vertices in

W . So, degG (x) d 1 + k

nk
2

1+k =

n+k2
,
2

which is a contradiction to the

hypothesis.
If G is simple and diam(G) = 1, then G = Kn and so k1 (G) = n 1 = (G).
The next results shows that simple graphs with diameter 2 also attain maximum
possible edge-connectivity.
Theorem 2.22 (J. Plesink, 1975). If G is simple and diam(G) = 2, then k1 (G) =
(G).
Proof. (Technique of two-way counting) Let F be a a minimum edge-cut; so
|F | = k1 (G). Then G contains exactly two components, say [A] and [B] such that
[A, B] = F . Let |A| = a and |B| = b.
If there exists some pair of vertices x A and y B such that [x, B] = and
[A, y] = , then dist(x, y) 3, contrary to the hypothesis. So, [x, B] 6= , for every
x A or [A, y] 6= , for every y B. For definiteness, let [x, B] 6= , for every x A.

55

2.3. Connectivity
y

x
edge-cut
F

Figure 2.15: Two components [A] and [B] of G F .

Therefore,
k1 = |F | =

|[x, B]|

xA

1 = a.

(2.1)

xA

We next estimate |F |, using the following equation and deduce that k1 .

dG (x) = d[A] (x) + |[x, B]|,

k1 = |F | =

|[x, B]|

xA

dG (x) d[A] (x), by (2.2)

xA

a a(a 1), since d[A] (x) a 1, for every x A

= + (a 1) a(a 1)
= + (a 1)( a)
+ (a 1)(k1 a), since k1 , by Theorem 2.18
, since a 1, and k1 a, by (2.1).
Since k1 , for every graph (Theorem 2.18), the result follows.

(2.2)

56

Module 2. Connected graphs and shortest paths

2.4

Weighted graphs and shortest paths

In any network, the links are associated with band widths or lengths or

capacities. In discrete mathematics all these parameters are called the weights
of the links.

Weighted graphs

Definitions.
A pair (G, W), where G is a graph and W : E(G) R is any function is called
a weighted graph; W(e) is called the weight of e. We assume that W(e) 0,
for every edge e.
Convention: Any unweighted graph G is treated as a weighted graph with W(e)
= 1, for every edge e.
P
If H is a subgraph of G, then its weight W(H) is defined to be eE(H) W(e).
P
So, the weight of a path P in G is eE(P ) W(e). It is called the weighted length
of P .
The weighted distance dist(u, v) between two given vertices u and v in a
weighted graph (G, W) is defined as

min{W(P ) : P is a (u, v)-path}, if u and v are connected,

dist(u, v) =

,
if u and v are not connected.
We often drop the adjective weighted to reduce the writing.
In the graph of Figure 2.16:

The
The
The
The

weight
weight
weight
weight

of
of
of
of

G is 14.5.
the path (u, a, v, c, x, e, y) is 12.
the path (u, a, v, d, x, e, y) is 4.5.
the path (u, b, x, e, y) is 5.

2.4. Weighted graphs and shortest paths

57

u
(a, 1)

(c, 8)

v
(d, 0.5)

(b, 2)
x (e, 3) y

Figure 2.16: A weighted graph (G, W), where the weight of an edge is shown next to
its label.

The shortest (u, y)-path is (u, a, v, d, x, e, y); so d(u, y) = 4.5; however, in

the underlying unweighted graph, d(u, y) = 2.

If G is a connected weighted graph, define d : V (G) V (G) R by d(u, v) =

dist(u, v), for every u, v V (G).
Theorem 2.23. If G is a connected weighted graph with non-negative edge weights,
then the following hold.
1. d(u, v) 0, for every u, v V (G).
2. d(u, v) = 0, if and only if u = v or W(u, v) = 0.
3. d(u, v) = d(v, u), for every u, v V (G).
4. d(u, v) d(u, x) + d(x, v), for every u, v, x V (G).

Proof. Exercise.

In many real world network problems, one is often required to find the shortest
distance and a shortest path between two given nodes. In graph theoretic terminology,
these two problems can be modeled as follows:
Design an algorithm to find the shortest distance and a shortest path between two
given vertices in a given weighted graph.

58

Module 2. Connected graphs and shortest paths

We describe two well-known such algorithms. It is assumed that the edge

weights are non-negative.

Dijkstras shortest path algorithm (1959)

It is a one-to-all algorithm in the sense that given any vertex u0 V (G), the

algorithm outputs the distance between u0 and every other vertex. However, it can be
easily modified into an all-to-all algorithm or to a many-to-many algorithm. It is
based on the principle that if (u0 , e1 , u1 , e2 , u2 , . . . , uk1 , ek , uk ) is a shortest (u0 , uk )path, then (u0 , e1 , u1 , e2 , u2 , . . . , uk1 ) is a shortest (u0 , uk1 )-path.
Description of the algorithm
Input: A weighted graph (G, W) and a vertex u0 V (G).
If a pair of vertices u and v are non-adjacent it is assumed that they are joined
by an edge of large weight, say 2W(G) , denoted .
Output: The weighted distance d(u0 , x), for every x V (G).
Remark.
It is a labeling process where every vertex x is dynamically labeled l(x) and at
the termination of the algorithm, l(x) indicates d(u0 , x).
Each vertex x is associated with an array of 3 fields x

l(x)

p(x) , where

p(x) is the parents of x.

Step 1: Initialization
l(u0 ) 0; p(u0 ) = u0 ; l(x) and p(x) = N U LL, for every vertex x 6= u0 ;
S {u0 }; i 0.
Step 2: Computation
If S = V goto Step 4;
Else, for each x V S do:

59

2.4. Weighted graphs and shortest paths

(i) If l(x) > l(ui ) + W(ui , x), replace l(x) by l(ui ) + W(ui , x); p(x) ui .
Else, retain l(x) and p(x).
(ii) Compute min{l(x) : x V S}.
(iii) Designate any vertex for which minimum is attained in (ii) as ui+1 .

(If there is more than one vertex for which the minimum is attained, you can
designate any such vertex as ui+1 .)
Step 3: Recursion
S S {ui+1 }; i i + 1; goto step 2.
Step 4: Output l(x) as d(u0 , x), and the array P (x, u0 ) = (x, p(x), p2 (x), . . . , u0 ), for
each x V (G) and STOP.
In the following, we illustrate the algorithm by taking a weighted graph.
b
1
Initialization:
V ertexx
l(x)

a
0

5
6

u0 = a

c
2

u0 = a, p(a) = a, S = {a}; V S =
{b, c, d, e}.

Figure 2.17: The input graph and its initialization.

Iteration 1:
b
x
l(x)

a
0

b
1

c
6

d
8

5
6

min{l(x) : x V S} = 1;
l(b) = 1; p(b) = a, S = {a, b};
V S = {c, d, e}, P = (b, p(b)) = (b, a).

8
d

e
4

60

Module 2. Connected graphs and shortest paths

Iteration 2:
b
x

l(x)

b
1

c
6

d
8

5
6

min{l(x) : x V S} = 3;

l(e) = 3; p(e) = b, S = {a, b, e};

2
e
4

V S = {c, d}, P = (e, b, a).

Iteration 3:

b
x

l(x)

b
1

c
6

d
7

5
6

min{l(x) : x V S} = 6;

l(c) = 6; p(c) = b, S = {a, b, e, c};

2
e
4

V S = {d}, P = (c, a).

Iteration 4:

b
x

l(x)

b
1

c
6

d
7

5
6

min{l(x) : x V S} = 7;
l(d) = 7; p(d) = e; S = {a, b, e, c, d};
V S = , P = (d, e, b, a).

e
4

We stop the algorithm and declare the labels l(x) shown in the above table as
d(a, x).
The shortest (a, b)-path is (a, b).
A shortest (a, c)-path is (a, c). The reader may notice that (a, b, c) is also a
shortest (a, c)-path.
The shortest (a, d)-path is (a, b, e, d).
The shortest (a, e)-path is (a, b, e).

2.4. Weighted graphs and shortest paths

61

Floyd-Warshall shortest path algorithm (1962)

It is a all-to-all algorithm in the sense that given a weighted graph (G, W),

the algorithm outputs the shortest distance d(x, y), for every pair (x, y) of vertices.
The algorithm makes use of a recursion formula proved below.
Theorem 2.24 ((Floyd and Warshall, 1962)). Let (G, W) be a weighted graph on
vertices labeled 1, 2, . . . , n. Define

The weighted length of a shortest (i, j)-path with all its internal vertices
k
dij =
from {1, . . . , k}; this path need not contain every vertex from {1, . . . , k}.
Then,
k1
k1
dkij = min{dk1
ij , dik + dkj }.

Proof. Let P be a shortest (i, j)-path with all its internal vertices from {1, . . . , k};
so its length l(P ) = dkij . Two cases arise.
Case 1: k is not an internal vertex of P .
So P is a (i, j)-path with all its internal vertices from {1, 2, ..., k 1}. Hence,
by defintion dkij = l(P ) = dk1
ij .
k
P1
i

P2
j

Figure 2.18: k is an internal vertex of P(i, j).

Case 2: k is an internal vertex of P .
In this case, P consists of two subpaths P1 (i, k) and P2 (k, j), where P1 is a
shortest (i, k)-path with all its internal vertices from {1, 2, . . . , k 1} and P2 is a

62

Module 2. Connected graphs and shortest paths

shortest (k, j) path with all its internal vertices from {1, 2, . . . , k 1}. So, l(P1 ) =
k1
dk1
ik , l(P2 ) = dkj . Hence,

k1
dkij = l(P ) = l(P1 ) + l(P2 ) = dk1
ik + dkj .

k1
The two cases imply that l(P ) is either dk1
or dk1
+ dkj
, whichever is minimum.
ij
ik
k1
So, dkij = min {dk1
+ dk1
ij , dik
kj }.

Remarks. By the definition of dkij , it may be observed that

d0ij := The weighted length of a shortest (i, j)-path with no internal vertices; so
the path is (i, j).
dnij := The weighted length of a shortest (i, j)-path in G.
dnii := 0.
The input for the algorithm is an n n matrix W (G) = [Wij ], called the
weighted matrix , where

0,

Wij =
W(i, j),

if i = j,
if i 6= j and i, j are adjacent,
if i 6= j and i, j are non-adjacent.

The output is the n n matrix [dnij ], whose (i, j)th entry is the length of a
shortest (i, j)-path.
Description of Floyd-Warshall algorithm
Input: A weighted graph (G, W) on vertices 1, 2,. . . , n.
Step 1: Initial: D0 W (G)
Step 2: Recursion:
for k = 1 to n do

63

2.4. Weighted graphs and shortest paths

for i = 1 to n do
for j = 1 to n do
k1
k1
dkij min{dk1
ij , dik + dkj }.

Step 3: Output Dn = [dnij ].

Remarks.

An advantage of the algorithm is that it requires very little knowledge of program coding.
The algorithm can be modified to output a shortest (x, y)-path; see exercises.

We again take the graph shown in Fig. 2.17 and illustrate the algorithm with
vertices labeled a = 1, b = 2, c = 3, d = 4 and e = 5. In the following, we show the
sequence of matrices D0 , D1 , D2 , D3 , D4 , D5 successively generated by the algorithm.

b
1

5
6

u0 = a

c
2

e
4

d
Figure 2.19: The input graph G.

Input matrix W(G) = D0 = [d0ij ].

64

Module 2. Connected graphs and shortest paths

Output matrix D =

a=1

b=2

c=3

d=4

e=5

[d1ij ]

after one (i, j)-loop, where d1ij = min{d0ij , d0i1 + d01j }

indicates the length of a shortest (i, j)-path with internal vertices from {1 = a}.
a

a=1

b=2

c=3

d=4

e=5

Output matrix after 2nd (i, j) loop, where d2ij = min {d1ij , d1i2 + d12j } indicates
the length of a shortest (i, j)-path with internal vertices from {1 = a, 2 = b}.
a

a=1

b=2

c=3

d=4

e=5

Output matrix after the 3rd (i, j) loop, D3 = [d3ij ], where d3ij = min{d2ij , d2i3 + d23j }
indicates the length of a shortest (i, j)-path with internal vertices from {1 = a, 2 =
b, 3 = c}.

65

2.4. Weighted graphs and shortest paths

a

a=1

b=2

c=3

d=4

e=5

th

Output matrix after the 4 (i, j) loop, D =

[d4ij ],

where d4ij = min{d3ij , d3i4 + d34j }

indicates the length of a shortest (i, j)-path with internal vertices from {1 = a, 2 =
b, 3 = c, 4 = d}.
a

a=1

b=2

c=3

d=4

e=5

Output matrix after the 5th (i, j) loop, D5 = [d5ij ], where d5ij = min{d4ij , d4i4 + d44j }
indicates the length of a shortest (i, j)-path with internal vertices from {1 = a, 2 =
b, 3 = c, 4 = d, 5 = e} = The length of a shortest (i, j)-path.
a

a=1

b=2

c=3

d=4

e=5

66

Module 2. Connected graphs and shortest paths

Exercises
1. Draw 3 mutually non-isomorphic graphs on 6 vertices and 5 edges, which do
not contain cycles.
2. Give an example of a 3-regular graph on 10 vertices in which the minimum
length of a cycle is 5.
3. Show that any two longest paths in a connected graph have a vertex in common.
Does this assertion hold for a disconnected graph?
4. If C is a cycle in G, then an edge of G which joins two non-consecutive vertices
of C is a called a chord of C. For example, (2, 5) is a chord of the 5-cycle
(1, 2, 3, 4, 5, 1). Show that if G has an odd cycle then it has an odd cycle
without chords.
5. Let G be a triangle-free graph and let C be a cycle of minimum length in G.
Show that every vertex in V (G) V (C) is adjacent with at most two vertices
of C.
6. If G is simple, connected, incomplete and n 3, then show that G has three
vertices u, v, w such that (u, v), (v, w) E(G) but (u, w)
6 E(G).
7. Give an example of a graph G such that
(a) every two adjacent vertices lie on a common cycle,
(b) there exists two adjacent edges that do not lie on a common cycle.
8. Let G be a graph. Define a relation R on V (G) as follows. If u, v V (G),
then u R v iff there exists a path connecting u and v. Show that R is an
equivalence relation on G. What are the induced subgraphs [V1 ], [V2 ], . . . , [Vp ],
where V1 , V2 , . . . , Vp are the equivalence classes?
, then show that G is connected. Give an example
9. If G is simple and (G) n1
2
of a disconnected simple graph G on 8 vertices with (G) = 3.


10. If m > n1
and G is simple, then show
that G is connected. For each n 1,
2
find a disconnected graph with m = n1
.
2
11. If deg(u) + deg(v) p 1, for every pair of non-adjacent vertices in a simple
graph G , then show that (i) G is connected, (ii) diam(G) 2 and (iii) G has
no cut-vertices.
12. Let G be a simple graph on vertices v1 , v2 , . . . , vn . Show that

67

2.4. Weighted graphs and shortest paths

(i) If every G vi is disconnected, then G is also disconnected.

(ii) If n 3 and G vi , G vj are connected, for some i, j {1, 2, . . . , n},

i 6= j, then G is connected. Does this hold if n = 2?
13. Show the following for a connected graph G:
(i) c(G v) deg(v), for every v V (G).
(ii) If every vertex in G is of even degree, then c(G v) 21 deg(v), for every
v V (G).
14. Let G ba a 2-connected simple graph. Let H be the simple graph obtained from
G by adding a new vertex y and joining it with at least 2 vertices of G. Show
that H is 2 connected.
15. Show that if G contains a closed walk of odd length, then it contains a cycle.
16. Show that G is connected iff every entry in I + A + A2 + + An1 is non-zero.
17. Find the maximum number of edges in a simple graph G which has girth 6.
18. Show that a k-regular simple graph with girth four has at least 2k vertices;
draw such a graph on 2k vertices.
19. Show that a k-regular simple graph of girth five has at least k 2 + 1 vertices. In
addition, if G has diameter two, then show that it has exactly k 2 + 1 vertices.
Draw such a graph on 2k vertices.
20. Prove or disprove: If G is a connected graph with cut-vertices and if u and v
are vertices of G such that d(u, v) = diam(G), then no block of G contains both
u and v.
21. Show that every graph with a cut-vertex has at least two end-blocks. (A block
H of G is called an end-block if it contains exactly one cut-vertex of G.)
22. Draw the following simple graphs:
(a) A graph on 10 vertices with 3 components that has maximum number of
edges.
(b) A connected graph (on at most 10 vertices) which has exactly 3 cut-vertices
and exactly 2 cut-edges.
23. Show that every k-connected graph G has at least

nk
2

edges.

68

Module 2. Connected graphs and shortest paths

24. If G is a 2-connected graph, then show that for some (x, y) E(G), G x y
is connected.
25. If the average degree of a connected graph G is greater than two, prove that G
has at least two cycles.
26. Draw connected spanning subgraphs H1 , H2 and H3 of the graph G (shown
below) having diameters 2,3 and 4 respectively and with minimum number of
edges.
1
5

3
G

27. Give an example of a graph with the following properties or explain why no
such example exists.
(i) A 4-connected graph that is not 3-connected.
(ii) A 3-connected graph that is not 4-connected.
(iii) A 2-edge-connected graph that is not 3-edge-connected.
(iv) A 3-edge-connected graph that is not 2-edge-connected.
28. (a) If G is disconnected, then show that Gc is connected. Is the converse true?
(b) If G is simple, show that G or Gc has diameter 3.
(c) If G is self-complimentary, show that 2 diam(G) 3.
29. For any two graphs G1 and G2 , show the following.
(a) k0 (G1 G2 ) = 0.
(b) k0 (G1 + G2 ) = min{k0 (G1 ) + n(G2 ), k0 (G2 ) + n(G1 )}.
(c) k1 (G1 G2 ) = 0.
(d) k1 (G1 + G2 ) = (G1 + G2 ).
30. Give an example of a graph G with the following properties or state why such
examples do not exist.
(a) k0 (G) = 3, k1 (G) = 4 and (G) = 5

2.4. Weighted graphs and shortest paths

69

(b) k0 (G) = 2, k1 (G) = 2 and (G) = 4

(c) k0 (G) = 3, k1 (G) = 3 and (G) = 2
(d) k0 (G) = 3, k1 (G) = 2 and (G) = 4
31. Prove or disprove:
(i) If G is a graph with k0 (G) = k 1, then G U is disconnected, for every
set U of k vertices.
(ii) If G is a connected graph and U is a minimum vertex-cut, then G U
contains exactly two components.
(iii) If G is a graph on n vertices and W = {u V (G) : deg(u) = n 1}, then
(a) W K(G), for every vertex-cut K(G) of G.
(b) every edge-cut of G contains an edge incident with a vertex in W .
32. Find the connectivity and edge-connectivity of the d-cube Qd .
33. Prove that if G is a simple r-regular graph, where 0 r 3, then k0 (G) =
k1 (G). Does it hold for multi-graphs? Find the minimum positive integer r for
which there exists an r-regular graph G such that k0 (G) 6= k1 (G).
34. Find the minimum positive integer r for which there exists a r-regular graph
such that k1 (G) k0 (G) + 2.
35. If G is simple and (G) n 2, then show that k0 (G) = (G).
36. If G is simple and (G) n2 , then show that k1 (G) = (G).
37. If G is a simple graph with (G)

n+1
,
2

then show that G is 3-vertex connected.

38. If G is simple and has no even cycles, then show that each block of G is either
K2 or an odd cycle.
39. Draw a network N with 7 nodes and with minimum number of links satisfying
the following conditions. Justify that your network has minimum number of
links.
(i) N contains no self-loops and multiple links.
(ii) If any two nodes fail, the remaining 5 healthy nodes can communicate
along themselves.

70

Module 2. Connected graphs and shortest paths

40. Let G be an incomplete simple graph on n vertices with vertex connectivity

k. If deg(v) 13 (n + 2k 2), for every vertex v, and S is a vertex-cut with k
vertices, then find the number of components in G S.
41. If G is a connected graph, then G2 has vertex set V(G) and two vertices u, v
are adjacent in G2 iff the distance between u and v in G is 1 or 2.
(a) Draw (P6 )2 , where P6 is the path on 6 vertices.
(b) If G is connected, show that G2 is 2-connected.
42. Let G be a simple graph with exactly one cycle. Find all possible values of the
vertex connectivity and edge connectivity of G. Justify your answer.
43. Use Dijkstras algorithm to compute a shortest path from the vertex a to every
other vertex in the edge weighted graph shown below. Show the weighted paths
generated at each step of the algorithm.
b

d
2

1
a

10

5
c

44. Find the entry in the first row and second column of the matrix generated after
applying one iteration of the Floyd-Warshall algorithm to the weighted graph
shown below.
d 4 c
6

2
a 1 b

45. If k0 (G) 3, then show that k0 (G e) 2, for every edge e.