CS1231 Chapter 11

Graphs

11.1 Paths
Warning 11.1.1. There are several commonly used, conflicting sets of terminologies for
graphs. Always check the definitions being used when looking into the literature.

Definition 11.1.2. Let G be an undirected graph, where G = (V, E).

(1) Denote by V(G) and E(G) the set of all vertices and the set of all edges in G respectively,
i.e.,
V(G) = V and E(G) = E.

(2) When there is no risk of ambiguity, we may write an edge {x, y} as xy.

(3) The graph G is finite if V(G) is finite, else it is infinite.

Definition 11.1.3. Let G, H be undirected graphs,.

(1) We say that H is a subgraph of G, or G contains H (as a subgraph), if V(H) ⊆ V(G)
and E(H) ⊆ E(G).

(2) A proper subgraph of G is a subgraph H of G such that H ̸= G.

Example 11.1.4. Consider the graph G, where

V(G) = {b, d, h, k, m, s},

E(G) = {bd, bh, bs, ds, hk, hs, ks, mm, ss}.

Here is a drawing of G.
b d

s m

h k

The graphs G1 , G2 , where

V(G1 ) = {b, d, h, k, m, s}, V(G2 ) = {b, d, h, m, s},

E(G1 ) = {bd, bs, hk, hs}, E(G2 ) = {bd, bh, ds, hs, mm},

93
are subgraphs of G. Here are drawings of G1 and G2 respectively.

b d b d

s m h m

h k s

The graph G3 , G4 , where

V(G3 ) = {1, 2, 3, 4, 5, 6}, V(G4 ) = {b, d, h, m, s},

E(G3 ) = {12, 13, 24, 35}, E(G4 ) = {bd, bs, dh, hs, mm},

are not subgraphs of G because V(G3 ) ̸⊆ V(G) and E(G4 ) ̸⊆ E(G). Here are drawings of G3
and G4 respectively.

2 4 b d

1 6 s m

3 5 h

Definition 11.1.5. Let G be an undirected graph, and u, v be vertices in G. A path between

u and v in G is a subgraph of G of the form


{x0 , x1 , . . . , xℓ }, {x0 x1 , x1 x2 , . . . , xℓ−1 xℓ } ,

where the x’s are all different and ℓ ∈ N, satisfying u = x0 and v = xℓ . Here ℓ is called the
length of the path. When there is no risk of ambiguity, we may denote the subgraph above
by x0 x1 . . . xℓ .

Remark 11.1.6. (1) Informally speaking, a path links two vertices in a graph via a se-
quence of edges, each joined to the next, that has no repeated vertex.
(2) Some consider paths of infinite length. We do not.
Example 11.1.7. Consider the graph G from Example 5.3.8. Define

P = dbshk and Q = dshb.

Then P is a path of length 4 between d and k in G, and Q is a path of length 3 between b

and d in G. Here are drawings of P and Q respectively.

b d b d

s s

h k h

The graphs H1 and H2 , where

H1 = dbsshk and H2 = bshksd

are not paths in G because s is in three edges in H1 , and four edges in H2 . (Note that each
vertex in a path is in at most two edges in the path.) Here are drawings of H1 and H2

94
respectively.

b d b d

s s

h k h k

Remark 11.1.8. Consider again the graph G from Example 5.3.8.

(1) The subgraph ({s}, {}), which we may write as s, is a path of length 0 in G. It is
essentially the vertex s with no edge, not even a loop.
(2) The subgraph ({s, h}, {sh}), which we may write as sh, is a path of length 1 in G. It is
essentially the edge sh.

s s

Figure 11.1: A path of length 0 (left) and a path of length 1 (right)

Exercise 11.1.9. How many paths are there between 1 and 3 in the undirected graph G  11a
with the following drawing?
3 c

2 b

1 a

Briefly explain your answer.

Lemma 11.1.10. Let G be an undirected graph and u, v, w be vertices in G. Suppose there

are a path P between u and v in G, and a path Q between v and w in G. Then there is a
path between u and w in G.

u = x0
P

ys+1 ys
xt

... v = xk = y0
Q
w = yℓ ...

Figure 11.2: Combining paths

95
Proof. Let P = x0 x1 . . . xk and Q = y0 y1 . . . yℓ , so that k, ℓ ∈ N and

x0 = u, xk = v = y0 , w = yℓ .

As xk = y0 ∈ V(Q), we know some t ∈ {0, 1, . . . , k} satisfies xt ∈ V(Q). Let t be the smallest

element of {0, 1, . . . , k} such that xt ∈ V(Q). By the smallestness of t, none of x0 , x1 , . . . , xt−1
is in V(Q). So if s ∈ {0, 1, . . . , ℓ} such that xt = ys , then

x0 x1 . . . xt ys+1 ys+2 . . . yℓ

is a path between u and w in G.

Remark 11.1.11. In the proof of Lemma 11.1.10 above, the existence of the required t is
guaranteed by the Well-Ordering Principle. In more details, we know k is an element of

{t ∈ {0, 1, . . . , k} : xt ∈ V(Q)}.

This set is thus a nonempty subset of N, and hence must have a smallest element by the
Well-Ordering Principle. Similar applications of the Well-Ordering Principle can be found in
the proof of Theorem 11.2.5 below.

11.2 Cycles
Definition 11.2.1. Let G be an undirected graph.
(1) A cycle in G is a subgraph of G of the form


{x1 , x2 , . . . , xℓ }, {x1 x2 , x2 x3 , . . . , xℓ−1 xℓ , xℓ x1 } ,

where the x’s are all different and ℓ ∈ N⩾3 . Here ℓ is called the length of the cycle.
When there is no risk of ambiguity, we may denote the subgraph above by x1 x2 . . . xℓ x1 .
(2) An undirected graph is cyclic if it has a loop or a cycle; else it is acyclic.

Remark 11.2.2. (1) Informally speaking, a cycle in a graph is a sequence of at least three
edges, each joined to the next, and the last joined to the first, that has no repeated
vertex.
(2) By definition, a cycle has at least three vertices (and thus at least three edges). There-
fore, in no sense can a loop be a cycle.
Example 11.2.3. Consider the graph G from Example 5.3.8. Define the graphs C, D by

C = shks and D = sdbhs.

Then C is a cycle of length 3 in G, and D is a cycle of length 4 in G. Here are drawings of

C and D respectively.

b d

s s

h k h

The graphs H3 and H4 , where

H3 = shs and H4 = bshksdb,

96
are not cycles in G because H3 has only two vertices, and s is in four different edges in H4 .
(Note that every cycle by definition has at least three vertices, and each vertex in a cycle is
in exactly two edges in the cycle.) Here are drawings of H3 and H4 respectively.

b d

s s

h h k

Example 11.2.4. (1) The graphs H1 and H2 from Example 11.1.7 are both cyclic because
the former has a loop {a} and the latter has a cycle C as defined in Example 11.2.3.
(2) The graph G1 from Example 11.1.4 and the graph Q from Example 11.1.7 are acyclic.

Theorem 11.2.5. An undirected graph with no loop is cyclic if and only if it has two vertices
between which there are two distinct paths.

yt
xr
xs
P
xr−1
u ... v
yr−1
Q
yr ...

Figure 11.3: Constructing a cycle from two paths between u and v

Proof. Let G be an undirected graph with no loop.

(⇒) Assume G is cyclic. According to the definition of cyclic graphs, as G has no loop,
it must have a cycle, say,
x1 x2 . . . xℓ x1 .
From this, we find two paths between x1 and xℓ :

x1 xℓ and x1 x2 . . . xℓ .

These two paths are distinct because the first one has two vertices and the second one has
at least three vertices as ℓ ⩾ 3.
(⇐) Let u, v ∈ V(G) with two distinct paths between them, say,

P = x0 x1 . . . xk and Q = y0 y1 . . . yℓ ,

where x0 = u = y0 and xk = v = yℓ . If the two paths are of different lengths, then let us use
the name Q for the longer of the two paths. This makes k ⩽ ℓ.
As P ̸= Q, we know xi ̸= yi for some i ∈ {0, 1, . . . , k}. Let r be the smallest element
of {0, 1, . . . , k} such that xr ̸= yr . Here r ̸= 0 because x0 = y0 . So the smallestness of r
tells us xr−1 = yr−1 . It follows that amongst xr−1 , yr−1 , xr , yr , only xr−1 and yr−1 are equal
because all the x’s are different and all the y’s are different.
Recall xk = yℓ . So some s ∈ {r, r + 1, . . . , k} makes xs ∈ {yr , yr+1 , . . . , yℓ }. Let s be the
smallest element of {r, r + 1, . . . , k} that makes xs ∈ {yr , yr+1 , . . . , yℓ }. By the smallestness
of s, none of xr , xr+1 , . . . , xs−1 is equal to any of yr , yr+1 , . . . , yℓ .

97
 Let t ∈ {r, r + 1, . . . , ℓ} that makes xs = yt . As xr ̸= yr , either s ̸= r or t ̸= r. So

xr−1 xr . . . xs yt−1 yt−2 . . . yr yr−1

has at least three vertices, and thus is a cycle in G.

Explanation of why xi ̸= yi for some i ∈ {0, 1, . . . , k} in the proof above (extra

material). Suppose not. Then xi = yi for all i ∈ {0, 1, . . . , k}. In particular, this tells us
yℓ = v = xk = yk . So k = ℓ as the y’s are all different. This implies P = Q, which contradicts
our condition that P and Q are distinct, as required. ■

11.3 Connectedness
Definition 11.3.1. An undirected graph is connected if there is a path between any two
vertices.

Example 11.3.2. (1) The graphs H1 , H2 from Example 11.1.7 are connected, as one can
verify exhaustively.
(2) The graphs G1 , G2 from Example 11.1.4 are not connected, because there is no path
between d and m in G1 and in G2 .
Exercise 11.3.3. Which of the following are drawings of connected graphs?  11b
(a) (b) (c) (d)

Definition 11.3.4. Let G be an undirected graph. A connected component of G is a maximal

connected subgraph of G, i.e., it is a connected subgraph H of G such that no connected
subgraph of G contains H as a proper subgraph.

Example 11.3.5. Consider the graph G from Example 11.1.4. The following are respectively
drawings of two connected components Hs and Hm of G.

b d

s m

h k

The graph G1 from Example 11.1.4 is not a connected component of G because it is not
connected. The graph D from Example 11.2.3 is not a connected component of G because it
is a subgraph of the connected subgraph Hs of G above with two fewer edges ss and bh.

Proposition 11.3.6. Let G be an undirected graph. Then every vertex v in G is in some

connected component of G.

Proof. Define the subgraph H of G by setting

V(H) = {x ∈ V(G) : there is a path between v and x in G} and

E(H) = {xy ∈ E(G) : x, y ∈ V(H)}.

98
We know v ∈ V(H) because ({v}, {}) is a path between v and v. To finish the proof, we
show that H is a connected component of G.
For the connectedness, let a, b ∈ V(H). Use the definition of V(H) to find paths

vx1 x2 . . . xk and vy1 y2 . . . yℓ

in G where xk = a and yℓ = b. Note that each xi , yj ∈ V(H) because vx1 x2 . . . xi and

vy1 y2 . . . yj are paths in G. Thus each xi xi+1 , yj yj+1 ∈ E(H) by the definition of E(H). It fol-
lows that vx1 x2 . . . xk and vy1 y2 . . . yℓ are paths in H. As xk = a and yℓ = b, Lemma 11.1.10
then gives us a path between a and b in H.
Let H + be a connected subgraph of G contains H as a subgraph. We want to show
H = H. The definition of subgraphs tells us already V(H) ⊆ V(H + ) and E(H) ⊆ E(H + ).
+

So it remains to show V(H + ) ⊆ V(H) and E(H + ) ⊆ E(H).

Take any x ∈ V(H + ). As v ∈ V(H) ⊆ V(H + ) and H + is connected, there is a path
between v and x in H + , hence in G. So x ∈ V(H) by the definition of V(H).
Take any xy ∈ E(H + ). Then x, y ∈ V(H + ) ⊆ V(H) by the previous paragraph. As
xy ∈ E(H + ) ⊆ E(G), the definition of E(H) tells us xy ∈ E(H).

Theorem 11.3.7. Let u, v be vertices in an undirected graph G. Then there is a path

between u and v in G if and only if there is a connected component of G that has both u
and v in it.

a Q2
Hu b

Q1

u v

Figure 11.4: A connected component plus a path

Proof. (⇒) Assume there is a path between u and v in G, say,

P = x0 x1 . . . xℓ ,

where u = x0 and v = xℓ . Use Proposition 11.3.6 to find
a connected component Hu of G

that has u in it. Define H = V(Hu ) ∪ V(P ), E(Hu ) ∪ E(P ) . We claim that H is a connected
subgraph of G. From this, we will deduce H = Hu using the maximality of the connected
component Hu ; thus v ∈ V(P ) ⊆ V(H) = V(Hu ).
Take a, b ∈ V(H). As V(H) = V(Hu ) ∪ V(P ), we have three cases.
Case 1: suppose a, b ∈ V(Hu ). As Hu is connected, there is a path between a and b in Hu ,
hence in H.
Case 2: suppose a, b ∈ V(P ). Say a = xr and b = xs , where r ⩽ s. Then a path between
a and b in H is xr xr+1 . . . xs .

99
Case 3: suppose one of a, b is in Hu and another is in P . Say a ∈ V(Hu ) and b ∈
V(P ). On the one hand, as Hu is connected, and a, u ∈ V(Hu ), one can find a path,
say Q1 , between a and u in Hu , hence in H. On the other hand, if b = xt where
t ∈ {0, 1, . . . , ℓ}, then Q2 = x0 x1 . . . xt a path between u and b in H. Combining Q1
and Q2 using Lemma 11.1.10, we get a path between a and b in H.
(⇐) Assume there is a connected component, say H, of G that has both u and v in it.
As H is connected, there is a path between u and v in H, hence in G.

Tutorial exercises
An asterisk (*) indicates a more challenging exercise.
11.1. Let us look into the notion of complete graphs. Fix n ∈ N.
Definition. A complete graph on n vertices, denoted Kn , is an undirected graph, with
exactly n vertices and with no loop, in which there is an edge between any pair of
distinct vertices.

(a) Draw K1 , K2 , K3 , and K4 . There is no need to label the vertices in your drawings.
(b) How many edges are there in Kn ? Explain your answer briefly.

11.2. Consider the undirected graphs G with V(G) = {a, b, c}.

(a) How many such graphs are there?
(b) How many of them have no loop?
(c) How many of them have a cycle?
(d) How many of them are cyclic?
Briefly explain your answers.
11.3. Two graphs of the same shape are considered unequal if their vertices are labelled
differently. This is sometimes undesirable. Sometimes we want to consider two graphs
as the same if (and only if) they are equal after a relabelling of the vertices. This notion
of sameness is called isomorphism in mathematics.
Definition. An isomorphism from an undirected graph G1 to an undirected graph G2
is a bijection f : V(G1 ) → V(G2 ) such that for all x, y ∈ V(G1 ),

{x, y} ∈ E(G1 ) ⇔ {f (x), f (y)} ∈ E(G2 ).

An undirected graph G1 is said to be isomorphic to an undirected graph G2 if there is

an isomorphism from G1 to G2 .
Example. The following are drawings of isomorphic graphs:

1 2 3 1

4 3 2 4

One isomorphism from the left graph to the right graph is the function f : {1, 2, 3, 4} →
{1, 2, 3, 4} satisfying

f (1) = 3, f (2) = 1, f (3) = 4, f (4) = 2.

It can be verified as in Tutorial Exercise 8.3 that the isomorphism relation on a set of
graphs is an equivalence relation.

100
 (a) Which of the graphs drawn below are isomorphic? Which are not isomorphic?

1 2 1 2 1 2 3 2
6 7 6 7 5 6 4 1

8 3 8 3 8 7 5 8
5 4 5 4 4 3 6 7

(i) (ii) (iii) (iv)

Briefly explain your answer.

(b) Let n ∈ {2, 3, 4}. How many undirected graphs are there with exactly n vertices
and with no loop if we count isomorphic graphs as one?

11.4. The aim of this exercise is to investigate in what sense the connected components form
a partition of an undirected graph.
(a) Is it true that, for all undirected graphs G with at least one vertex, the set {V(H) :
H is a connected component of G} is a partition of V(G)?
(b) Is it true that, for all undirected graphs G with at least one edge, the set {E(H) :
H is a connected component of G} is a partition of E(G)?
Prove that your answers are correct.
11.5. In this exercise, we look into the relationship between an undirected graph with no loop
and its complement, in the sense defined below.
Definition. The complement of an undirected graph G with no loop, denoted G, is the
undirected graph with no loop defined by V(G) = V(G) and, for all distinct x, y ∈ V(G),

xy ∈ E(G) ⇔ xy ̸∈ E(G).

(a) Consider the graph whose drawing is as follows.

3 2

4 1

5 6

Draw the complement of this graph.

∗
(b) Prove that, for all undirected graphs G with at least one vertex but with no loop,
either G is connected or G is connected.

11.6. (Induction corner) Someone attempts to prove that

(x1 + x2 + · · · + xn )2 = x1 2 + x2 2 + · · · + xn 2

for all x1 , x2 , . . . , xn ∈ R and all n ∈ Z+ as follows.

We proceed by Strong MI on n. Let P (n) be the predicate

(x1 + x2 + · · · + xn )2 = x1 2 + x2 2 + · · · + xn 2 for all x1 , x2 , . . . , xn ∈ R

over Z+ .
(Base step) P (1) is true because x1 2 = x1 2 for every x1 ∈ R.

101
 (Induction step) Let k ∈ Z+ such that P (1), P (2), . . . , P (k) are true. Take
any z1 , z2 , . . . , zk , zk+1 ∈ R. Then

(z1 + z2 + · · · + zk + zk+1 )2
= (z1 + z2 + · · · + zk )2 + zk+1 2 by P (2);
2 2 2 2
= z1 + z2 + · · · + zk + zk+1 by P (k).

So P (k + 1) is true.
Hence ∀n ∈ Z+ P (n) is true by Strong MI.

Note that (2 + 2)2 = 42 = 16 ̸= 8 = 4 + 4 = 22 + 22 . What is wrong with the proof

above?

Further exercises
11.7. Let P be a path in an undirected graph. Prove that |V(P )| = |E(P )| + 1.
11.8. Let C be a cycle in an undirected graph. Prove that |V(C)| = |E(C)|.

11.9. We verify in this exercise that a connected component of an undirected graph must
inherit all the possible edges from that graph.
Let G be an undirected graph, and H be a connected component of G. Prove that

E(H) = {xy ∈ E(G) : x, y ∈ V(H)}.

11.10. Intuitively, undirected graphs that have many edges relative to the number of vertices
must be connected. In this exercise, we investigate what “many” may mean here.

(a)∗ Let n ∈ N and G be an undirected graph with exactly n vertices and with no loop.
Prove that, if |E(G)| > n−1


2 , then G is connected.
(b) How many connected undirected graphs are there with exactly 4 vertices and with
no loop in which the number of edges is at most 4−1


2 if we count isomorphic
graphs as one?

102