Lecture 12

Graphs and Trees

…And indeed, the weakest of houses is the house of the spider, if they only knew.
(Quran 29:41)

332
 Motivation

• Graphs are used in many applications in mathematics,

computer science, and similar other fields
• Many problems can be formulated by using graphs
93
and then solved by graph algorithms and techniques 101
• Example: 71
• Consider the road network of a country, where 75
each city is a node (or a point), and the roads 89
among them are lines. See right-side picture 67
• Each line has labels corresponding to the distance
• Suppose you want to find the minimum travelling 57 97
distance among two cities
• This can be solved by graph algorithms

333
 Definitions: Graph

• A graph consists of a set of vertex and a set of edges Madinah

• A graph G is written as G=(V,E), where V is the set of
Tabuk
vertices and E is the set of edges Badr
• An edge is a connection between two vertices
• An edge represents that the two vertices are related
• Example:
• In this graph G, vertices are cities
• An edge means that there is a road between two
Riyadh
cities
Mecca
• If no road between two cities, then no edge
• For example, a road exists from Madinah to Badr Khaybar
• Whereas, there is no road from Riyadh to Badr G

334
 Definitions: Adjacency

• An edge e=(u,v) connects two vertices u and v a

• In that case, u and v are called adjacent to each other
• u and v are also called the end points of e b
• e is also called incident to u and incident to v c
• Adjacent vertices are also called neighbors
• Example: In the right-side graph G:
• a and c are adjacent because of the edge (a, c)
• c and e are not adjacent d
• d has four neighbors b, a, f, e
e
• Exercise: See a map of your country, draw the graph
f
of road networks among major cities, find which
G
cities are adjacent

335
 Definitions: Degree b
a

c
• Degree of a vertex x is the number of edges incident e
to x. It is written as deg(x)
• Example: In the right-side graph G1, d
G1
• deg(a) = 3
• deg(b) = 2
• deg(c) = 2 a f
b
• deg(d) = 2
• deg(e) = 3
c
• Exercise:
e
• In this graph G2, find the degree of all vertices
• Draw a graph with 4 vertices, each of odd degree G2
d
• Draw a graph of six vertices each having degree 3

336
 Definitions: Degree

• A multi graph has multiple edges among vertices

• In a multi graph, degree of a vertex counts all edges a
• A vertex is called isolated if no edge is incident to it b
• An isolated vertex has degree zero
c
• A loop is an edge if its two end points are the same
• A loop is counted twice as the degree of the vertex
• Example: The right-side graph G is a multi graph with
d
• deg(a)=4, deg(b)=4, deg(c)=2, deg(d)=1, deg(e)=5,
deg(f)=0
f e
• a has a loop and f is an isolated vertex
• Exercise: Draw a multi graph with two vertices and
G
with loops such that each vertex has degree six

337
 Handshaking Theorem
G1
• Let us see a puzzle
• Look at these three graph G1, G2 and G3 in the right-
side pictures
• They are arbitrarily taken
• For each of them, the sum of the degree is:
• G1: 1+2+3 = 6 G2
• G2: 1+1+2+2+4 = 10
• G3: 0+2+3+3 = 8
• Do you see any similarity among these sum values?
• Yes, they are all even!
• Is there any other similarities?
• Yes! Next slide … G3

338
 Handshaking Theorem
G1
• For each of them, the sum of the degree is twice the
number of edges:
• G1: 1+2+3 = 6 = 2*3 (number of edges in G1 is 3)
• G2: 1+1+2+2+4=10=2*5 (number of edges in G2 is 5)
• G3: 0+2+3+3 = 8 = 2*4 (number of edges in G1 is 4)
• Is this true for any graph? G2
• Yes!
• This is called handshaking theorem:
• For any graph, sum of degree of vertices are twice
the number of edges
• Mathematically, for a graph G = (V,E)
𝐯∈𝐕 𝐝𝐞𝐠𝐫𝐞𝐞 𝐯 𝟐|𝐄| G3

339
 Proof of Handshaking Theorem

• Consider a graph G = (V,E) and an edge e = (u,v) of G

• e is counted as a degree two times for two vertices,
1
once for u and once for v (even if u=v when e is a loop) 1
• So, e contributes 1 to the degree of u and 1 to the 1
degree of v (see right-side picture) 1
1
• So, when the degree of all vertices are summed up
1
(including the degree of u and v), e contributes 2
1
to that sum
• Similarly, every other edge contributes 2 to the sum 1 1 1
• Over all edges of E, total contribution is 2|E| 1 1
• There is no other contribution to the degree sum
G
• So, degree sum = 2 * number of edges

340
 Directed Graphs

• In a directed graph, each edge e = (u,v) has a direction

from u to v
• u is the initial vertex and v is the terminal vertex b c
• v is said to be adjacent to u
• There are two types of degree of a vertex in a directed
graph: indegree (indeg for short) and outdegree d
(outdeg for short)
• Indeg(v) is the number of edges with terminal vertex v
f
• Outdeg(v) is the number of edges with initial vertex v e
• Example: In the right-side figure, indeg(b) = indeg(c) =
2, indeg(e) = indeg(f) = 1, indeg(d) = 0, Outdeg(b) = G
outdeg(c) = outdeg(e) = 2, outdeg(d) = outdeg(f) = 0

341
 Handshaking Theorem

• Handshaking theorem holds for directed graphs too G1

• The theorem is expressed in terms of indegree and
outdegree as follows:
Sum of indegrees = sum of outdegrees = number of edges
• Mathematically, for a directed graph G = (V,E)
𝐯∈𝐕 𝐢𝐧𝐝𝐞𝐠 𝐯 𝐯∈𝐕 𝐨𝐮𝐭𝐝𝐞𝐠 𝐯 |𝐄| G2
• For example, in G2 in the right-side picture
• Sum of indeg = 0+0+1+1+3 = 5
• Sum of outdeg = 0+1+1+1+2 = 5
• Number of edges = 5
• So, the theorem holds
G3
• Exercise: Verify handshaking theorem for G1 and G3

342
 Complete Graphs K1

• A graph whose edges do not have any direction is called K2

an undirected graph
• A graph without a loop or multiple edge is called simple
• A complete graph is a simple undirected graph where
each pair of vertices has an edge
• In a complete graph, no more edges can be added without
K3
violating its simplicity
• A complete graph with n 1 vertices is represented as Kn
• Example: Right-side pictures show K1, K2, K3, K5
• Kn has C(n,2)=n(n-1)/2 edges, as there are C(n,2) ways to
chose two vertex for an edge. Each vertex has degree n-1
• Exercise: Draw K4 and K6 and verify they have C(n,2) edges K5

343
 Walk, Path, Cycle

• A walk in a graph is a sequence of vertex so that the

consecutive vertices in the sequence are adjacent
• A path is a walk where no two vertices are same, except
may be the first and last vertices
b c
• A cycle is a path when the first and last vertices are
same z
• Example: In the right-side picture,
• (p, b, c, z, r, b, c, r) is a walk p r
• (p, b, c, p, z, r, p) is not a walk, as (c,p) is not adjacent G
• (z, c, r, b) is a path
• (z, c, r, b, c, r, z) is not a path as c and r are repeated
• (b, z, c, b) and (b, c, z, p, r, b) are two cycles

344
 Walk, Path, Cycle

• Length of a walk, path or cycle is the number of edges

• Length of a walk can be infinite
• Whereas, length of paths and cycles are finite, because
of avoiding vertex repetition b c
• Example: In the right-side graph G,
z
• (b) is a walk as well as a path of length zero
• (b, r) is a path of length one p
r
• (b, c, z, p, r, b) is a cycle of length five, and this is a G
maximum-length cycle in G
• (b, c, b, c, b, c, … is an infinite walk
• Exercise: Find all paths of length three in G
• Exercise: Find all cycles of length five in G

345
 b c z

Bipartite Graphs
p r

• A graph is bipartite if its vertices can be divided into two b z

partitions such that there is no edge within a partition
• It means that all edges are between the two partitions p r
• Example: The top-right graph is a bipartite graph c
• One partition (shaded box) contains (b, c, z), and the
other partition (shaded box) contains (p, r)
• Sometimes graphs are bipartite but are not drawn as
bipartite. Such graphs can be redrawn as bipartite
• Example: This graph is same as the graph above it
• Example: This graph is a star graph, where a center
vertex is connected to every other vertex, and there is no
more edges. This graph is bipartite and is redrawn is here

346
 Bipartite Graphs

• Example: Odd length (3, 5, 7, …) cycles are not bipartite

• Because its edges cannot be partitioned into two
groups without having an edge within a partition
a b
• Example: Drawing the cycle of length three as bipartite is c
not possible. Because, one partition will always have an
edge within itself. See the top picture in the right-side f d
• Exercise: Try to draw cycles of length 5, 7, 9, 11, … as e
bipartite graphs. Why that would not be possible?
• Example: Even length (4, 6, 8, 10, …) cycles are bipartite
a c e
• Because alternate vertices can be in same partition
• Example: A cycle of length 6 is redrawn as bipartite here
• Exercise: Draw cycles of length 8, 10, 12 as bipartite b d f

347
 Bipartite Graphs

• Exercise: Draw this path as bipartite

• Exercise: Explain why a path of length 1 which is not
a cycle is bipartite (no matter whether the length of the
path is even or odd)
• A bipartite graph is complete is every vertex in one
partition is adjacent to every vertex in other partition
• A complete bipartite graph is represented as Km,n
• m and n are the number of vertices in two partitions
• Example: K1,1 and K2,4 are drawn here
• Degree sum of Km,n is 2mn. Why? Think yourself!
• Exercise: Draw K1,5, K3,3, K4,7. Verify that their degree K1,1 K2,4
sum is equal to 2mn

348
 Graph Representation b c

z
• So far, we have seen graphs by their pictures p r
• But graphs are efficiently represented to perform
different operations and computations on them
• We shall see three useful representations of graphs:
• Adjacency list Vertices List of adjacent
• Adjacency matrix vertices
• Incidence matrix b c, r, z, p
• In an adjacency list of a graph, each vertex c b, r, z
has a list of adjacent vertices (in any order) p b, r, z, p
• Adjacency list does not work for graphs with r c, z, p, b
multiple edges
z b, c, r, p
• Example: Right-side picture shows an example

349
 Adjacency List

• Adjacency lists work for directed graphs too

• Example: See below for a directed graph and its
adjacent list
Vertices List of adjacent
Adjacency list
vertices
b c b c, e Adjacency
c c, f matrix
d
d f Incidence
e b matrix
f
e f
• Exercise: In the above example, reverse the direction of
the edges of the graph and rewrite the adjacency list

350
 a b
Adjacency Matrix c
d e

• Adjacency matrix of a graph of n vertices is an a b c d e

n n matrix M a 0 1 1 1 1
• Each vertex is assigned to a unique row and b 1 0 1 0 1
column of M with same row and column number c 1 1 0 1 1
• If (u,v) is an edge, then M[u,v] and M[v,u] is d 1 0 1 1 1
assigned to 1, otherwise they are assigned to 0 e 1 1 1 1 0
• Example: See the top-right corner M
• Exercise: Draw the graph whose adjacency matrix
0 0 0 0 0
is this matrix
0 0 1 0 1
• Exercise: Draw the adjacency matrix of the
0 1 0 1 1
following graph 0 0 1 1 1
0 1 1 1 0

351
 a b c d e
a b
a 0 1 0 1 2
Adjacency Matrix c b 1 0 0 0 0

d e c 0 0 0 0 0
d 1 0 0 2 1
2 0 0 1 0
• For a multi graph, M[u,v] and M[v,u] get the value e
of the number of edges between u and v
• Example: A multi graph and its adjacency matrix is
b c
given in the top-right corner
d
• Example: For a directed graph, for an edge (u,v),
only M[u,v] gets 1. See this example f
e
• Exercise: Find an adjacency matrix in the previous
example by reversing the direction of all edges b c d e f
b
• Exercise: Why an adjacency matrix for an 0 1 0 1 0
c 0 1 0 0 1
undirected graph is symmetric? That means,
M[u,v] = M[v,u] for all u, v? Is it also true for a d 0 0 0 0 1
e 1 0 0 0 0
directed graph? (See the right-side examples)
f 0 0 0 0 0

352
 e1
Incidence Matrix a e2 b
e5 e3
e6
c
e7 e4
d
• Incidence matrix of a simple graph of n vertices and m e8
e
edges is an n m matrix M
• Each vertex is assigned to a unique row e1 e 2 e3 e4 e 5 e6 e7 e8
• Each edge is assigned to a unique column a 1 1 0 0 1 1 0 0
• For each edge ei=(u,v), M[u,ei] = M[v,ei] = 1 b 0 1 1 1 0 0 0 0
• All other cells of M are 0 c 0 0 1 0 1 0 1 0
• Example: See the right-side picture d 0 0 0 0 0 1 1 1
• Each column in an incidence matrix has e 1 0 0 1 0 0 0 1
exactly two 1s
• Exercise: Incidence matrix for non-simple graphs can
also be defined. But we do not see that here
• Exercise: Write incidence matrices for K5 and K3,4

353
 a

Weighted Graphs b 93 99
71 c
75
89
• A graph is called weighted when its edges have weights d
67
• They can be represented by adjacency matrix
57
• If (u,v) is an edge, then M[u,v] and M[v,u] contains the 97 f
weight of the edge (u,v) e
• Example: See the right-side example
• Weight of an edge can be negative a b c d e f
• For example, in a graph of road network, a 0 0 0 93 0 99
a negative weight means you get some b 0 0 71 75 0 89
incentives if you use that road c 0 71 0 0 97 0
• Weighted graphs arise in many applications, d 93 75 0 0 57 67
such as in shortest path computation e 0 0 97 57 0 0
f 99 89 0 67 0 0

354
 Subgraphs
G
• A graph G’ is a subgraph of another graph G if the
vertex and edge sets of G’ are subsets of the
vertex and edge sets of G
• In another way to say, if G’ is available within G
• Example: In the right-side picture, G1, G2, G3, G1
G4 and G5 are some subgraphs of G G2
• A graph is a subgraph of itself, such as G4 G3
• G2 does not look like anything within G, but it
is a cycle of length 5, and G has many cycles of
length five (find yourself one such cycle in G) G5
• G5 is a subgraph of G with all vertices of G
but with no edge from G G4

355
 Subgraphs
G
• Example: In the right-side picture, G1, G2, G3,
and G4 are not subgraphs of G. Because,
• G1 has a cycle of length 3, but G does not
have any cycle of length 3 (verify yourself)
• G2 has seven edges, but G has six edges G1
G2
• G3 is K4, but G does not have any K4
• G4 has a vertex of degree 4, but G does
not have any vertex with degree 4
• Exercise: Explain whether the following five
G4 G3
graphs are subgraphs of G or not.

356
 a b
Connected Graphs c
e
d
G2
• A graph is connected if any two vertices has a path G1
• Example: In the top-right corner, G1 is connected,
but G2 is not because many pairs of vertices have a b
no path, such as there is no path from a to c e
d c
• Connected components of a graph G are the
maximal connected subgraphs of G
• A maximal connected subgraph of G means no
more vertex or edge from G can be added to the
subgraph so that it remains connected
• Example: See two connected components of G2
• Example: A connected graph has itself as the only
component. See here

357
 d
a b
Connected Graphs G c
e
d

• Example: In the right-side example, C1 a b

• C3 is a connected component of G
• C1 and C2 are not connected components of G a d
• Because, C1 and C2 can be made bigger by d
e
c
adding more vertex and edge. For example, C2 C3
they can be merged together to get a bigger
connected subgraph of G. This violates the
condition of “maximal connected”. See here b d
• Exercise: Find the connected components of the a
following two graphs G1 and G2: e c
d
C3

G1
G2
358