MODULE IV
Graph Theory
Basics of Graphs
Definition. A graph G = (V , E) consists of V , a nonempty set of vertices (or nodes) and E, a
set of edges. Each edge has either one or two vertices associated with it, called its
endpoints. An edge is said to connect its endpoints.
Definition. A directed graph (or digraph) (V, E) consists of a nonempty set of vertices V and
a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of
vertices. The directed edge associated with the ordered pair (u, v) is said to start at u and
end at v.
Graph Terminology
Type Edges Multiple Edges Allowed? Loops Allowed?
Simple graph Undirected No No
Multigraph Undirected Yes No
Pseudograph Undirected Yes Yes
Simple directed Directed No No
graph
Directed multigraph Directed Yes Yes
Mixed graph Directed and Yes Yes
Undirected
For some models we may need a graph where some edges are undirected, while others are
directed. A graph with both directed and undirected edges is called a mixed graph. For
example, a mixed graph might be used to model a computer network containing links that
operate in both directions and other links that operate only in one direction. This
terminology for the various types of graphs is summarized in Table 1. We will sometimes
use the term graph as a general term to describe graphs with directed or undirected edges
(or both), with or without loops, and with or without multiple edges. At other times, when
the context is clear, we will use the term graph to refer only to undirected graphs.
Definition: Degree of a vertex v in a graph is defined as the number of edges associated to it.
HANDSHAKING THEOREM
Let G = (V , E) be an undirected graph with m edges. Then 2𝑚 = ∑𝑣∈𝑉 𝑑𝑒𝑔(𝑣).
{HIINT: Every edge is counted twice when we are summing up the degrees.}
Example. How many edges are there in a graph with 10 vertices each of degree six?
Solution: Because the sum of the degrees of the vertices is 6 · 10 = 60, it follows that 2m =
60 where m is the number of edges.
Therefore, m = 30.
Example: An undirected graph has an even number of vertices of odd degree.
Definition: When (u, v) is an edge of the graph G with directed edges, u is said to be
adjacent to v and v is said to be adjacent from u. The vertex u is called the initial vertex of
(u, v), and v is called the terminal or end vertex of (u, v). The initial vertex and terminal
vertex of a loop are the same.
Definition: In a graph with directed edges the in-degree of a vertex v, denoted by deg−(v), is
the number of edges with v as their terminal vertex. The out-degree of v, denoted by
deg+(v), is the number of edges with v as their initial vertex.
Example: Find the in-degree and out-degree of each vertex in the graph G with directed
edges shown in Figure 2.
Solution: The in-degrees in G are deg−(a) = 2, deg−(b) = 2, deg−(c) = 3, deg−(d) = 2,
deg−(e) = 3, and deg−(f ) = 0.
The out-degrees are deg+(a) = 4, deg+(b) = 1, deg+(c) = 2, deg+(d) = 2, deg+(e) = 3, and
deg+(f ) = 0.
Theorem: Let G = (V , E) be a graph with directed edges. Then
∑𝑣∈𝑉 deg − (𝑣) = ∑𝑣∈𝑉 deg + (𝑣) = |𝐸|.
Complete Graphs: A complete graph, denoted by 𝐾𝑛 , is a simple graph that contains exactly
one edge between each pair of distinct vertices. The graphs 𝐾𝑛 , for n = 1, 2, 3, 4, 5, 6, are
displayed in Figure 3. A simple graph for which there is at least one pair of distinct vertex
not connected by an edge is called noncomplete.
Exercises
1. Draw graph models, stating the type of graph (from Table 1) used, to represent airline
routes where every day there are four flights from Boston to Newark, two flights from
Newark to Boston, three flights from Newark to Miami, two flights from Miami to Newark,
one flight from Newark to Detroit, two flights from Detroit to Newark, three flights from
Newark to Washington, two flights from Washington to Newark, and one flight from
Washington to Miami, with
a) an edge between vertices representing cities that have a flight between them (in either
direction).
b) an edge between vertices representing cities for each flight that operates between them
(in either direction).
c) an edge between vertices representing cities for each flight that operates between them
(in either direction), plus a loop for a special sightseeing trip that takes off and lands in
Miami.
d) an edge from a vertex representing a city where a flight starts to the vertex representing
the city where it ends.
e) an edge for each flight from a vertex representing a city where the flight begins to the
vertex representing the city where the flight ends.
2. Draw the acquaintanceship graph that represents that Tom and Patricia, Tom and Hope,
Tom and Sandy, Tom and Amy, Tom and Marika, Jeff and Patricia, Jeff and Mary, Patricia
and Hope, Amy and Hope, and Amy and Marika know each other, but none of the other
pairs of people listed know each other.
3. We can use a graph to represent whether two people were alive at the same time. Draw
such a graph to represent whether each pair of the mathematicians and computer scientists
with biographies in the first five chapters of this book who died before 1900 were
contemporaneous.
4. Can we have a graph with 5 edges, 2 vertices of degree 3 and 4 vertices of degree 2?
Connected components
WALK: Sequence of edges and vertices with repetition allowed
TRAIL: Sequence of edges and vertices with repetition of edges not allowed
PATH: Sequence of edges and vertices with repetition of edges and vertices not allowed
Example: In the simple graph shown in Figure 1, a, d, c, f , e is a simple path of length 4,
because {a, d}, {d,c}, {c, f }, and {f, e} are all edges. However, d, e, c, a is not a path, because
{e, c} is not an edge. Note that b, c, f , e, b is a circuit of length 4 because {b, c}, {c, f }, {f, e},
and {e, b} are edges, and this path begins and ends at b. The path a, b, e, d, a, b, which is of
length 5, is not simple(a walk to be precise) because it contains the edge {a, b} twice.
Example: Which of the following are paths in the directed graph shown in Figure 1: a, b, e,
d; a, e, c, d, b; b, a, c, b, a, a, b; d,c; c, b, a; e, b, a, b, a, b, e? What are the lengths of those
paths? Which of the paths in this list are circuits?
Solution: Because each of (a, b), (b, e), and (e, d) is an edge, a, b, e, d is a path of length
three.
Because (c, d) is not an edge, a, e, c, d, b is not a path.
Also, b, a, c, b, a, a, b is a path of length six because (b, a), (a, c), (c, b), (b, a), (a, a), and (a, b)
are all edges.
We see that d,c is a path of length one, because (d, c) is an edge.
Also c, b, a is a path of length two, because (c, b) and (b, a) are edges.
All of (e, b), (b, a), (a, b), (b, a), (a, b), and (b, e) are edges, so e, b, a, b, a, b, e is a path of
length six.
The two paths b, a, c, b, a, a, b and e, b, a, b, a, b, e are circuits because they begin and end at
the same vertex.
The paths a, b, e, d; c, b, a; and d,c are not circuits.
Example. Let R be a relation on a set A. There is a path of length n, where n is a positive
integer, from a to b if and only if (a, b) ∈ Rn.
Proof: We will use mathematical induction. There is a path from a to b of length one if and
only if (a, b) ∈ R, so the theorem is true when n = 1.
Assume that the theorem is true for the positive integer n.
This is the inductive hypothesis.
There is a path of length n + 1 from a to b if and only if there is an element c ∈ A such that
there is a path of length one from a to c, so (a, c) ∈ R, and a path of length n from c to b, that
is, (c, b) ∈ Rn.
Consequently, by the inductive hypothesis, there is a path of length n + 1 from a to b if and
only if there is an element c with (a, c) ∈ R and (c, b) ∈ Rn. But there is such an element if
and only if (a, b) ∈ Rn+1.
Therefore, there is a path of length n + 1 from a to b if and only if (a, b) ∈ Rn+1.
Definition: An undirected graph is called connected if there is a path between every pair of
distinct vertices of the graph. An undirected graph that is not connected is called
disconnected. We say that we disconnect a graph when we remove vertices or edges, or
both, to produce a disconnected subgraph.
Example: The graph 𝐺1 in Figure 2 is connected, because for every pair of distinct vertices
there is a path between them (the reader should verify this). However, the graph 𝐺2 in
Figure 2 is not connected. For instance, there is no path in 𝐺2 between vertices a and d.
Theorem: There is a simple path between every pair of distinct vertices of a connected
undirected graph.
Example: What are the connected components of the graph H shown in Figure 3?
Solution: Graph H is the union of three disjoint connected subgraphs 𝐻1 , 𝐻2 , and 𝐻3 , shown
in Figure 3. These three subgraphs are the connected components of H.
Example:
Connected Components of Call Graphs: Two vertices x and y are in the same component of
a telephone call graph when there is a sequence of telephone calls beginning at x and
ending at y. When a call graph for telephone calls made during a particular day in the AT&T
network was analyzed, this graph was found to have 53,767,087 vertices, more than 170
million edges, and more than 3.7 million connected components. Most of these components
were small; approximately three-fourths consisted of two vertices representing pairs of
telephone numbers that called only each other. This graph has one huge, connected
component with 44,989,297 vertices comprising more than 80% of the total. Furthermore,
every vertex in this component can be linked to any other vertex by a chain of no more than
20 calls.
A cut vertex (articulation point) is a vertex whose removal (along with its incident edges)
increases the number of connected components of a graph, thereby disconnecting it.
Similarly, a cut edge (bridge) is an edge whose removal disconnects the graph. These
concepts are important in applications like communication networks, where such vertices
and edges represent critical points of failure.
Example1: Find the cut vertices in the graph A–B–C–D with an extra edge B–E.
Solution: If vertex B is removed, A becomes isolated and the remaining graph splits into
multiple parts, so B is a cut vertex. If C is removed, D becomes disconnected, so C is also a
cut vertex. Hence, the cut vertices are B and C.
Example2: Find the cut edges in the same graph.
Solution: Removing edge (A, B) isolates A, removing (B, C) breaks the graph into two parts,
removing (C, D) isolates D, and removing (B, E) isolates E. Hence, all edges in this graph are
cut edges (bridges).
Example3: Determine whether the cycle graph A–B–C–D–A has any cut vertices or cut
edges.
Solution: Removing any one vertex or edge still leaves the graph connected because
alternative paths exist. Therefore, this graph has no cut vertices and no cut edges.
Trees
Definition: A tree is a connected undirected graph with no simple circuits.
Example: Which of the graphs shown in Figure 2 are trees?
Solution: 𝐺1 and 𝐺2 are trees, because both are connected graphs with no simple circuits.
𝐺3 is not a tree because e, b, a, d, e is a simple circuit in this graph.
Finally, 𝐺4 is not a tree because it is not connected.
Definition: A pendant vertex (also called a leaf vertex) in graph theory is a vertex that has
degree 1, i.e., it is connected to exactly one other vertex.
Theorem: An undirected graph is a tree if and only if there is a unique simple path between
any two of its vertices.
Definition: A rooted tree is a tree in which one vertex has been designated as the root and
every edge is directed away from the root.
In a rooted tree, one vertex is chosen as the root and all edges are directed away from it. A
parent is a node that is directly connected above another node, while a child is the node
directly connected below it. For example, if there is an edge from node A to node B, then A
is the parent of B and B is the child of A. The root node has no parent, every other node has
exactly one parent, and a node can have multiple children. Nodes that share the same
parent are called siblings, and nodes with no children are called leaves.
Example: In the rooted tree T (with root a) shown in Figure 5, find the parent of c, the
children of g, the siblings of h, all ancestors of e, all descendants of b, all internal vertices,
and all leaves. What is the subtree rooted at g?
Solution: The parent of c is b. The children of g are h, i, and j .
The siblings of h are i and j . The ancestors of e are c, b, and a.
The descendants of b are c, d, and e.
The internal vertices are a, b, c, g, h, and j .
The leaves are d, e, f , i, k, l, and m.
The subtree rooted at g is shown in Figure 6.
Properties of Trees
Theorem: A tree with n vertices has n − 1 edges.
Theorem: Every tree has at least one pendant vertex.
Theorem: A full m-ary tree with i internal vertices contains n = mi + 1 vertices.
Exercises
1. Which of these graphs are trees?
2. Which of these graphs are trees?
3. Answer these questions about the rooted tree illustrated.
a) Which vertex is the root?
b) Which vertices are internal?
c) Which vertices are leaves?
d) Which vertices are children of j?
e) Which vertex is the parent of h?
f ) Which vertices are siblings of o?
g) Which vertices are ancestors of m?
h) Which vertices are descendants of b?
4. Prove that a tree with n vertices has exactly n−1 edges using mathematical induction.
HAMILTONIAN/EULERIAN WALKS
Definition: An Euler circuit in graph G is a simple circuit containing every edge of G. An
Euler path in G is a simple path containing every edge of G.
Example: Which of the undirected graphs in Figure 3 have an Euler circuit? Of those that do
not, which have an Euler path?
Solution: The graph 𝐺1 has an Euler circuit, for example, a, e, c, d, e, b, a.
Neither of the graphs 𝐺2 or 𝐺3 has an Euler circuit (the reader should verify this).
However, 𝐺3 has an Euler path, namely, a, c, d, e, b, d, a, b.
𝐺2 does not have an Euler path
Theorem: A connected multigraph with at least two vertices has an Euler circuit if and only
if each of its vertices has even degree.
Example: Many puzzles ask you to draw a picture in a continuous motion without lifting a
pencil so that no part of the picture is retraced. We can solve such puzzles using Euler
circuits and paths. For example, can Mohammed’s scimitars, shown in Figure 6, be drawn in
this way, where the drawing begins and ends at the same point?
Solution: We can solve this problem because graph G shown in Figure 6 has an Euler
circuit.
It has such a circuit because all its vertices have even degree.
We will use Algorithm 1 to construct an Euler circuit.
First, we form the circuit a, b, d, c, b, e, i, f, e, a.
We obtain the subgraph H by deleting the edges in this circuit and all vertices that become
isolated when these edges are removed.
Then we form the circuit d, g, h, j, i, h, k, g, f, d in H.
After forming this circuit we have used all edges in G.
Splicing this new circuit into the first circuit at the appropriate place produces the Euler
circuit a, b, d, g, h, j, i, h, k, g, f, d, c, b, e, i, f, e, a.
This circuit gives a way to draw the scimitars without lifting the pencil or retracing part of
the picture.
Theorem: A connected multigraph has an Euler path but not an Euler circuit if and only if it
has exactly two vertices of odd degree.
Definition: A simple path in a graph G that passes through every vertex exactly once is
called a Hamilton path, and a simple circuit in a graph G that passes through every vertex
exactly once is called a Hamilton circuit. That is, the simple path 𝑥0 , 𝑥1 , . . . , 𝑥𝑛−1 , 𝑥𝑛 in the
graph G = (V , E) is a Hamilton path if 𝑉 = {𝑥0 , 𝑥1 , . . . , 𝑥𝑛−1 , 𝑥𝑛 } and 𝑥𝑖 = 𝑥𝑗 for 0 ≤ i 0) is a
Hamilton circuit if 𝑥0 , 𝑥1 , . . . , 𝑥𝑛−1 , 𝑥𝑛 is a Hamilton path.
Example: Which of the simple graphs in Figure 10 have a Hamilton circuit or, if not, a
Hamilton path?
Solution: 𝐺1 has a Hamilton circuit: a, b, c, d, e, a.
There is no Hamilton circuit in 𝐺2 (this can be seen by noting that any circuit containing
every vertex must contain the edge {a, b} twice), but 𝐺2 does have a Hamilton path, namely,
a, b, c, d.
𝐺3 has neither a Hamilton circuit nor a Hamilton path, because any path containing all
vertices must contain one of the edges {a, b}, {e, f }, and {c, d} more than once.
DIRAC’S THEOREM:
If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is
at least n/2, then G has a Hamilton circuit.
ORE’S THEOREM:
If G is a simple graph with n vertices with n ≥ 3 such that deg(u) + deg(v) ≥ n for every
pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit.
PLANARITY
Definition: A graph is called planar if it can be drawn in the plane without any edges
crossing (where a crossing of edges is the intersection of the lines or arcs representing
them at a point other than their common endpoint). Such a drawing is called a planar
representation of the graph.
Example: Is 𝐾4 (shown in Figure 2 with two edges crossing) planar?
Solution: 𝐾4 is planar because it can be drawn without crossings, as shown in Figure 3
1. Which of these nonplanar graphs have the property that the removal of any vertex
and all edges incident with that vertex produces a planar graph?
a) 𝐾5 b) 𝐾6 c) 𝐾3,3 d) 𝐾3,4
GRAPH COLOURING
Definition: Coloring of a simple graph is the assignment of a color to each vertex of the
graph so that no two adjacent vertices are assigned the same color.
Definition: Chromatic number of a graph is the least number of colors needed for a coloring
of this graph. The chromatic number of a graph G is denoted by 𝜒 (𝐺).
FOUR COLOR THEOREM:
The chromatic number of a planar graph is no greater than four
Example: What are the chromatic numbers of the graphs G and H shown in Figure 3?
Solution: The chromatic number of G is at least three, because vertices a, b, and c must be
assigned different colors.
To see if G can be colored with three colors, assign red to a, blue to b, and green to c.
Then, d can (and must) be colored red because it is adjacent to b and c.
Furthermore, e can (and must) be colored green because it is adjacent only to vertices
colored red and blue, and f can (and must) be colored blue because it is adjacent only to
vertices colored red and green.
Finally, g can (and must) be colored red because it is adjacent only to vertices colored blue
and green. This produces a coloring of G using exactly three colors.
Figure 4 displays such a coloring.
Graph H is made up of the graph G with an edge connecting a and g.
Any attempt to color H using three colors must follow the same reasoning as that used to
color G, except at the last stage, when all vertices other than g have been colored.
Then, because g is adjacent (in H) to vertices colored red, blue, and green, a fourth color,
say brown, needs to be used.
Hence, H has a chromatic number equal to 4.
A coloring of H is shown in Figure 4.
Example: What is the chromatic number of 𝐾𝑛 ?
Solution: A coloring of 𝐾𝑛 can be constructed using n colors by assigning a different color to
each vertex.
Is there a coloring using fewer colors? The answer is no.
No two vertices can be assigned the same color, because every two vertices of this graph
are adjacent. Hence, the chromatic number of 𝐾𝑛 is n.
That is, χ (𝐾𝑛 ) = n. (Recall that 𝐾𝑛 is not planar when n ≥ 5, so this result does not
contradict the four color theorem.)
A coloring of 𝐾5 .
Example:
Scheduling Final Exams-How can the final exams at a university be scheduled so that no
student has two exams at the same time?
Solution: This scheduling problem can be solved using a graph model, with vertices
representing courses and with an edge between two vertices if there is a common student
in the courses they represent. Each time slot for a final exam is represented by a different
color.
The scheduling of exams corresponds to a coloring of the associated graph.
For instance, suppose there are seven finals to be scheduled. Suppose the courses are
numbered 1 through 7.
Suppose that the following pairs of courses have common students: 1 and 2, 1 and 3, 1 and
4, 1 and 7, 2 and 3, 2 and 4, 2 and 5, 2 and 7, 3 and 4, 3 and 6, 3 and 7, 4 and 5, 4 and 6, 5
and 6, 5 and 7, and 6 and 7.
The graph associated with this set of classes is shown.
The scheduling consists of a coloring of this graph. Because the chromatic number of this
graph is 4 (the reader should verify this), four time slots are needed.
Exercises
1. Which graphs have a chromatic number of 1?
2. What is the least number of colors needed to color a map of the United States? Do
not consider adjacent states that meet only at a corner. Suppose that Michigan is one
region. Consider the vertices representingAlaska and Hawaii as isolated vertices.
3. What is the chromatic number of 𝑊𝑛 ?
4. Show that a simple graph that has a circuit with an odd number of vertices in it
cannot be colored using two colors.
5. Schedule the final exams for Math 115, Math 116, Math 185, Math 195, CS 101, CS
102, CS 273, and CS 473, using the fewest number of different time slots, if there are
no students taking both Math 115 and CS 473, both Math 116 and CS 473, both Math
195 and CS 101, both Math 195 and CS 102, both Math 115 and Math 116, both Math
115 and Math 185, and both Math 185 and Math 195, but there are students in every
other pair of courses.
6. How many different channels are needed for six stations located at the distances
shown in the table, if two stations cannot use the same channel when they are
within 150 miles of each other?
GRAPH ISOMORPHISM
Two graphs 𝐺1 and 𝐺2 are said to be isomorphic to each other if there exists a one – to – one
correspondence between the vertex sets which preserves the adjacency of the vertices.
Problem. Establish the isomorphism for the following graphs
Soln.
Both the graphs G and H have
(i) Same number of vertices(5)
(ii) Same number of edges(5)
(iii) The degree sequences of G is 2, 2, 2, 2, 2
(iv) The degree sequences of H is 2, 2, 2, 2, 2
The adjacent matrix of G
𝑢1 𝑢2 𝑢3 𝑢4 𝑢5
𝑢1 0 1 0 0 1
𝑢2 1 0 1 0 0
𝐴(𝐺) = 𝑢3 0 1 0 1 0
𝑢4 0 0 1 0 1
𝑢5 ( 1 0 0 1 0)
𝑢1 𝑢2 𝑢3 𝑢4 𝑢5
𝑢1 0 1 0 0 1
𝑢2 1 0 1 0 0
𝐴(𝐻) = 𝑢3 0 1 0 1 0
𝑢4 0 0 1 0 1
𝑢5 ( 1 0 0 1 0)
∴ 𝐴(𝐺) = 𝐴(𝐻)
∴ G and H are isomorphic.
Problem. State the necessary condition for two graphs to be isomorphic show that the following
two graphs are isomorphic.
Soln.
Nessary Condition
Two graphs G and H are isomorphic if
(i) Same number of vertices(7)
(ii) Same number of edges(12)
(iii) The degree sequences of G is 1, 2, 3, 3, 4, 5, 6 = 24
(iv) The degree sequences of H is 1, 2, 3, 3, 4, 5, 6 = 24
The adjacent matrix of G is
0 0 0 0 0 0 1
0 0 0 0 0 1 1
0 0 0 0 1 1 1
A(G) = 0 0 0 0 1 1 1
0 0 1 1 0 1 1
0 1 1 1 1 0 1
(1 1 1 1 1 0 0)
The adjacency matrix of H is
0 0 0 0 0 0 1
0 0 0 0 0 1 1
0 0 0 0 1 1 1
𝐴(𝐻) = 0 0 0 0 1 1 1
0 0 1 1 0 1 1
0 1 1 1 1 0 1
(1 1 1 1 1 0 0)
∴ 𝐴(𝐺) = 𝐴(𝐻)
∴ G and H are isomorphic.
Problem. Establish the isomorphism of the following pair of graphs
Soln.
Clearly G and H have
(i) Same number of vertices (6)
(ii) Same number of edges (5)
(iii) Degree sequences
G : 1, 2, 3, 2, 1, 1
H: 1, 2, 2, 3, 1, 1
Since in a graph H, 𝑢4 is adjacent to two pendent vertices but in G there is no such vertex.
∴ we cannot define a mapping between G and H.
∴ 𝐺 is not isomorphic to H
Exercise Problems.
1. Determine the following graphs are isomorphic or not
2. Establish the isomorphism for the following graphs
Homomorphism
A homomorphism between two graphs is a mapping that preserves adjacency (edge
connection).
Let 𝐺1 = (𝑉1 , 𝐸1 ) and 𝐺2 = (𝑉2 , 𝐸2 ). A function 𝑓: 𝑉1 → 𝑉2 is called a graph homomorphism if
for every edge (𝑢, 𝑣) ∈ 𝐸1 , (𝑓(𝑢), 𝑓(𝑣)) ∈ 𝐸2
Note: Text and figures have been used from Rosen and other online sources where needed