Chapter 10 Graphs

Definition: A graph G = (V, E) consists of a nonempty set

V of vertices (or nodes) and a set E of edges. Each edge
has either one or two vertices associated with it, called
its endpoints. An edge is said to connect its endpoints.

Basic Types of GRAPH

• Simple Graph

• Multi Graph

• Pseudo Graph

• Null Graph

• Complete Graph

• Regular Graph
 Some Terminology
• In a simple graph each edge connects two different vertices and no two edges
connect the same pair of vertices.
• Multigraphs may have multiple edges connecting the same two vertices. When
m different edges connect the vertices u and v, we say that {u,v} is an edge of
multiplicity m.
• An edge that connects a vertex to itself is called a loop.
• A pseudograph may include loops, as well as multiple edges connecting the
same pair of vertices.

Example: a b Remark: There is no standard

This terminology for graph theory.
pseudograph So, it is crucial that you
has both understand the terminology
multiple edges being used whenever you read
and a loop. material about graphs.
c
 Directed Graphs
Definition: An directed graph (or digraph)
G = (V, E) consists of a nonempty set V of vertices
(or nodes) and a set E of directed edges (or arcs).
Each 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.

Remark:
• Graphs where the end points of an edge are not
ordered are said to be undirected graphs.
 Some Terminology (continued)

• A simple directed graph has no loops and no multiple edges.

a b
Example:
This is a directed graph
with three vertices and
four edges. c
• A directed multigraph may have multiple directed edges. When there are m
directed edges from the vertex u to the vertex v, we say that (u,v) is an
edge of multiplicity m.

Exampl
e:
multiplicity of (a,b) is 1 and the
In this directed multigraph the a b

multiplicity of (b,c) is 2.
c
 Graph Terminology: Summary
• To understand the structure of a graph and to build a graph
model, we ask these questions:
• Are the edges of the graph undirected or directed (or both)?
• If the edges are undirected, are multiple edges present that connect the
same pair of vertices? If the edges are directed, are multiple directed
edges present?
• Are loops present?
 10.1 Graphs and
Graph Models
• When we build a graph model, we use the appropriate type of graph to capture the
important features of the application.
• We illustrate this process using graph models of different types of computer networks.
In all these graph models, the vertices represent data centers and the edges represent
communication links.
• To model a computer network where we are only concerned whether two data
centers are connected by a communications link, we use a simple graph. This is the
appropriate type of graph when we only care whether two data centers are directly
linked (and not how many links there may be) and all communications links work in
both directions.
 Graph Models:
Computer Networks (continued)

• To model a computer network where we care about the

number of links between data centers, we use a multigraph.
 Graph Models: Computer Networks

• To model a computer network with diagnostic links at data

centers, we use a pseudograph, as loops are needed.
Graph Models: Computer Networks
• To model a network with multiple one-way links, we use a
directed multigraph. Note that we could use a directed graph
without multiple edges if we only care whether there is at least
one link from a data center to another data center.
 Graph Models: Social Networks
• Graphs can be used to model social structures based on
different kinds of relationships between people or groups.
• In a social network, vertices represent individuals or
organizations and edges represent relationships between
them.
• Useful graph models of social networks include:

• friendship graphs - undirected graphs where two people

are connected if they are friends (in the real world, on
Facebook, or in a particular virtual world, and so on.)
• collaboration graphs - undirected graphs where two
people are connected if they collaborate in a specific way
• influence graphs - directed graphs where there is an
edge from one person to another if the first person can
influence the second person ..
 Graph Models: Social
Networks
Example: A friendship graph where two people are
connected if they are Facebook friends.
 Graph Models: Social
Networks
Example: An influence graph
Applications to Information Networks
• Graphs can be used to model different types of networks that
link different types of information.
• In a web graph, web pages are represented by vertices and
links are represented by directed edges.

• A web graph models the web at a particular time.

• We will explain how the web graph is used by search engines in Section
11.4.
• In a citation network:

• Research papers in a particular discipline are represented by vertices.

• When a paper cites a second paper as a reference, there is an edge from
the vertex representing this paper to the vertex representing the second
paper.
 Transportation Graphs
• Graph models are extensively used in the study of
transportation networks.
• Airline networks can be modeled using directed
multigraphs where
• airports are represented by vertices
• each flight is represented by a directed edge from the vertex
representing the departure airport to the vertex representing the
destination airport
• Road networks can be modeled using graphs where
• vertices represent intersections and edges represent roads.
• undirected edges represent two-way roads and directed edges
represent one-way roads.
 Software Design Applications
• Graph models are extensively used in software design. We will
introduce two such models here; one representing the
dependency between the modules of a software application
and the other representing restrictions in the execution of
statements in computer programs.

• When a top-down approach is used to design software, the

system is divided into modules, each performing a specific task.
•
• We use a module dependency graph to represent the
dependency between these modules. These dependencies
need to be understood before coding can be done.
 Software Design Applications

• In a module dependency graph vertices represent software modules and

there is an edge from one module to another if the second module
depends on the first.

Example: The dependencies between the seven

modules in the design of a web browser are
represented by this module dependency graph.
 Software Design Applications
• We can use a directed graph called a precedence graph to
represent which statements must have already been executed
before we execute each statement.

• Vertices represent statements in a computer program

• There is a directed edge from a vertex to a second vertex if the second
vertex cannot be executed before the first

Example: This
precedence graph shows
which statements must
already have been
executed before we can
execute each of the six
statements in the
program.
 Biological Applications
• Graph models are used extensively in many areas of the biological
science. We will describe two such models, one to ecology and the
other to molecular biology.
• Niche overlap graphs model competition between species in an
ecosystem
• Vertices represent species and an edge connects two vertices when they
represent species who compete for food resources.
Example: This is the niche overlap graph for a forest ecosystem
with nine species.
 Biological Applications
• We can model the interaction of proteins in a cell using a protein
interaction network.
• In a protein interaction graph, vertices represent proteins and
vertices are connected by an edge if the proteins they represent
interact.
• Protein interaction graphs can be huge and can contain more than
100,000 vertices, each representing a different protein, and more
than 1,000,000 edges, each representing an interaction between
proteins
• Protein interaction graphs are often split into smaller graphs,
called modules, which represent the interactions between
proteins involved in a particular function.
 Biological Applications
Example: This is a module of the protein
interaction graph of
proteins that degrade RNA in a human cell.
 Graph Terminology
and
Special Types of

Section 10.2
Graphs

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Basic Terminology
Definition 1. Two vertices u, v in an undirected graph G are
called adjacent (or neighbors) in G if there is an edge e between
u and v. Such an edge e is called incident with the vertices u and
v and e is said to connect u and v.

Definition 2. The set of all neighbors of a vertex v of G = (V, E),

denoted by N(v), is called the neighborhood of v. If A is a subset
of V, we denote by N(A) the set of all vertices in G that are
adjacent to at least one vertex in A. So,

Definition 3. The degree of a vertex in a undirected graph is the

number of edges incident with it, except that a loop at a vertex
contributes two to the degree of that vertex. The degree of the
vertex v is denoted by deg(v).
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Degrees and Neighborhoods of
Vertices
Example: What are the degrees and neighborhoods of the vertices
in the graphs G and H?

Solution:
G: deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, deg(e) = 3, deg(g) = 0.
N(a) = {b, f }, N(b) = {a, c, e, f }, N(c) = {b, d, e, f }, N(d) = {c},
N(e) = {b, c , f }, N(f) = {a, b, c, e}, N(g) =  .
H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.
N(a) = {b, d, e}, N(b) = {a, b, c, d, e}, N(c) = {b}, N(d) = {a, b, e},
N(e) = {a, b ,d}.
 Handshaking Theorem
Theorem: If G is any graph, then the sum of the degrees of all the
vertices of G equals twice the number of edges of G.

COROLLARY: The total degree of G is an even number

FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Handshaking Theorem
Example: How many edges are there in a graph with 10 vertices of
degree six?

Solution: Because the sum of the degrees of the vertices is

6  10 = 60, the handshaking theorem tells us that 2m = 60.
So the number of edges m = 30.

Example: If a graph has 5 vertices, can each vertex have degree 3?

Solution: This is not possible by the handshaking theorem, because

the sum of the degrees of the vertices 3  5 = 15 is odd.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Theorms of Graph

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Degree of Vertices

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Directed Graphs (continued)
Definition: The in-degree of a vertex v, denoted deg−(v), is the
number of edges which terminate at v. The out-degree of v,
denoted deg+(v), is the number of edges with v as their initial
vertex. Note that a loop at a vertex contributes 1 to both the in-
degree and the out-degree of the vertex.
Example: In the graph G we have

deg−(a) = 2, deg−(b) = 2, deg−(c) = 3, deg−(d) = 2, deg−(e) = 3,

deg−+(f) = 0.
deg (a) = 4, deg+(b) = 1, deg+(c) = 2, deg+(d) = 2, deg+ (e) = 3,
deg+(f) = 0.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Special Types of Simple
Graphs:
Complete Graphs
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of
distinct vertices.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Special Types of Simple
Graphs:
A cycle C for nCycles
≥ 3 consists of n and v ,⋯ , v , and edges {v , v }, {v ,
vertices v , Wheels
v3} ,⋯ , {vn-1, vn}, {vn, v1}.
n 1 2 n 1 2 2

A wheel Wn is obtained by adding an additional vertex to a cycle Cn

for n ≥ 3 and connecting this new vertex to each of the n vertices in
Cn by new edges.
 Special Types of Graphs
and Computer Network
Architecture
Various special graphs play an important role in the design of computer
networks.

• Some local area networks use a star topology, which is a complete bipartite
graph K1,n ,as shown in (a). All devices are connected to a central control
device.
• Other local networks are based on a ring topology, where each device is
connected to exactly two others using Cn ,as illustrated in (b). Messages may
be sent around the ring.
• Others, as illustrated in (c), use a Wn – based topology, combining the
FREE:features of a star
For Complete topology[Link]
Playlist: and a ring topology.
For Code, Slide and Books: [Link]
 Special Types of Simple Graphs:
n-Cubes
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n vertices
representing all bit strings of length n, where there is an edge
between two vertices that differ in exactly one bit position.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Special Types of Graphs and
Computer Network
Architecture
• Various special graphs also play a role in parallel processing where
processors need to be interconnected as one processor may need the
output generated by another.
• The n-dimensional hypercube, or n-cube, Qn, is a common way to connect
processors in parallel, e.g., Intel Hypercube.
• Another common method is the mesh network, illustrated here for 16
processors.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Thanks
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Bipartite Graphs
Definition: A simple graph G is bipartite if V can be partitioned into two disjoint
subsets V1 and V2 such that every edge connects a vertex in V1 and a vertex in
V2. In other words, there are no edges which connect two vertices in V1 or in
V2.

• It is not hard to show that an equivalent definition of a bipartite graph is a

graph where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.

What is disjoint Set?

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Degree of Vertices

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Bipartite Graphs (continued)
Example: Show that C3 is not bipartite.
Solution: If we divide the vertex set of C3 into two
nonempty sets, one of the two must contain two vertices.
But in C3 every vertex is connected to every other vertex.
Therefore, the two vertices in the same partition are
connected. Hence, C3 is not bipartite.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Bipartite Graphs (continued)
Example: Show that C6 is bipartite.
Solution: We can partition the vertex set into
V1 = {v1, v3, v5} and V2 = {v2, v4, v6} so that every edge of C6 connects a vertex
in V1 and V2 .

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Bipartite Graphs

G is H is not bipartite since if we color a

bipartite red, then the adjacent vertices f and b
must both be blue.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Bipartite Graphs and Matchings
• Bipartite graphs are used to model applications that involve
matching the elements of one set to elements in another, for
example:
• Job assignments - vertices represent the jobs and the
employees, edges link employees with those jobs they have
been trained to do. A common goal is to match jobs to
employees so that the most jobs are done.
 Complete Bipartite Graphs
Definition: A complete bipartite graph Km,n is a graph that
has its vertex set partitioned into two subsets V1 of size m
and V2 of size n such that there is an edge from every
vertex in V1 to every vertex in V2.

Example: We display four complete bipartite graphs here.

 New Graphs from Old

where W ⊂ V and F ⊂ E. A subgraph H of G is a proper

Definition: A subgraph of a graph G = (V,E) is a graph (W,F),

subgraph of G if H ≠ G.
Example: Here we show K5 and one of its subgraphs.

Definition: Let G = (V, E) be a simple graph. The subgraph induced by a

subset W of the vertex set V is the graph (W,F), where the edge set F
contains an edge in E if and only if both endpoints are in W.
Example: Here we show K5 and the subgraph induced by W = {a,b,c,e}.
 New Graphs from Old
(continued)
simple graph with vertex set V1 ⋃ V2 and edge set E1 ⋃ E2. The union of G1
Definition: The union of two simple graphs G1 = (V1, E1) and G2 = (V2, E2) is the

and G2 is denoted by G1 ⋃ G2.

Example:

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Representations of Graphs
Section 10.3

Section Summary
•Adjacency Lists
•Adjacency Matrices
•Incidence Matrices
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Representing Graphs:
Adjacency Lists
Definition: An adjacency list can be used to represent a graph with no
multiple edges by specifying the vertices that are adjacent to each
vertex of the graph.

Example:

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Representing Graphs:
Adjacency Lists

Exampl
e:

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Representation of Graphs:
Adjacency Matrices
Definition: Suppose that G = (V, E) is a simple graph where |V| = n. Arbitrarily

respect to the listing of vertices, is the n × n zero-one matrix with 1 as its (i,
list the vertices of G as v1, v2, … , vn. The adjacency matrix AG of G, with

j)th entry when vi and vj are adjacent, and 0 as its (i, j)th entry when they are
not adjacent.

• In other words, if the graphs adjacency matrix is AG = [aij], then

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Adjacency Matrices
(continued)
Exampl When a graph is
e: sparse, that is, it has
few edges relatively
to the total number of
The
possible edges, it is
ordering
of vertices much more efficient
is a, b, c, d. to represent the
graph using an
adjacency list than an
The
ordering
adjacency matrix.
of But for a dense
vertices is graph, which includes
a, b, c, d. a high percentage of
possible edges, an
adjacency matrix is
Note: The adjacency matrix of a simple graph is symmetric, i.e., aij
preferable.
Also, since there are no loops, each diagonal entry aij for i = 1, 2,
= aji

3, …, n, is 0.
 Adjacency Matrices (continued)
• Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, j)th position of
the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or
if multiple loops are present at the same vertex), the (i, j)th entry
equals the number of edges connecting the pair of vertices.
• Example: We give the adjacency matrix of the pseudograph shown
here using the ordering of vertices a, b, c, d.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Representation of Graphs:
Incidence Matrices
Definition: Let G = (V, E) be an undirected graph with
vertices where v1, v2, … vn and edges e1, e2, … em. The
incidence matrix with respect to the ordering of V and E is
the n × m matrix M = [mij], where

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Incidence Matrices (continued)
Example: Simple Graph and Incidence Matrix
The rows
going from
top to bottom
represent v1
through v5
and the
columns
going from
left to right
represent e1
Example: Pseudograph and Incidence Matrix through e6.
The rows
going from top
to bottom
represent v1
through v5 and
the columns
going from
left to right
represent e
Connectivit
y
Section 10.4
 Paths
Informal Definition: A path is a sequence of edges that
begins at a vertex of a graph and travels from vertex to
vertex along edges of the graph. As the path travels along
its edges, it visits the vertices along this path, that is, the
endpoints of these.

Applications: Numerous problems can be modeled with

paths formed by traveling along edges of graphs such as:

• determining whether a message can be sent

between two computers.
• efficiently planning routes for mail delivery.
 Paths
Definition: Let n be a nonnegative integer and G an undirected graph. A path
of length n from u to v in G is a sequence of n edges e1, … , en of G for which
there exists a sequence x0 = u, x1, …, xn-1, xn = v of vertices such that ei has, for
i = 1, …, n, the endpoints xi-1 and xi.

• When the graph is simple, we denote this path by its vertex sequence
x0, x1, … , xn(since listing the vertices uniquely determines the path).
• The path is a circuit if it begins and ends at the same vertex (u = v)
and has length greater than zero.
• The path or circuit is said to pass through the vertices x1, x2, … , xn-1
and traverse the edges e1, … , en.
• A path or circuit is simple if it does not contain the same edge more
than once.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Paths (continued)

• a, d, c, f, e is a simple path of length 4.

Example: In the simple graph here:

• b, c, f, e, b is a circuit of length 4.
• d, e, c, a is not a path because e is not connected to c.

• a, b, e, d, a, b is a path of length 5, but it is not a simple

path.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Summary of WALK TRAIL
and PATH

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Connectedness in
Undirected Graphs
Definition: An undirected graph is called connected if there is a
path between every pair of vertices. 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: G1 is connected because there is a path between any pair

of its vertices, as can be easily seen. However G2 is not connected
because there is no path between vertices a and f, for example.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Connected and Strongly Connected
Components
in a Graph

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Euler and
Hamiltonian
Graphs
Section 10.5
 Euler and
Hamiltonian
Graphs
Section 10.5
Section Summary
•Euler Paths and Circuits
•Hamilton Paths and Circuits
•Applications of Hamilton Circuits
 Euler Graph, Paths and
Circuits
• The town of Kӧnigsberg, Prussia

In the 18th century seven bridges connected these regions.

(now Kalingrad, Russia) was divided into four sections by the branches of the Pregel river.

• People wondered whether it was possible to follow a path that crosses each bridge
exactly once and returns to the starting point.
• The Swiss mathematician Leonard Euler proved that no such path exists. This result is
often considered to be the first theorem ever proved in graph theory.
 Euler Paths and Circuits
Definition: An Euler circuit in a 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 G1, G2, and G3 has a Euler circuit?
Of those that do not, which has an Euler path?

Solution: The graph G1 has an Euler circuit (e.g., a, e, c, d, e, b, a). But, as can
easily be verified by inspection, neither G2 nor G3 has an Euler circuit. Note that
G3 has an Euler path (e.g., a, c, d, e, b, d, a, b), but there is no Euler path in G2,
which can be verified by inspection.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Euler Circuits and
Example:
Paths

G1 contains exactly two vertices of odd degree (b and d). Hence it has an Euler
path, e.g., d, a, b, c, d, b.

G2 has exactly two vertices of odd degree (b and d). Hence it has an Euler path,
e.g., b, a, g, f, e, d, c, g, b, c, f, d.

G3 has six vertices of odd degree. Hence, it does not have an Euler path.
 Necessary Conditions for Euler
Circuits and Paths
• An Euler circuit begins with a vertex a and continues with an edge
incident with a, say {a, b}. The edge {a, b} contributes one to deg(a).
• Each time the circuit passes through a vertex it contributes two to
the vertex’s degree.
• Finally, the circuit terminates where it started, contributing one to
deg(a). Therefore deg(a) must be even.
• We conclude that the degree of every other vertex must also be
even.
• By the same reasoning, we see that the initial vertex and the final
vertex of an Euler path have odd degree, while every other vertex
has even degree. So, a graph with an Euler path has exactly two
vertices of odd degree.
• In the next slide we will show that these necessary conditions are
also sufficient conditions.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
Algorithm for Constructing an Euler Circuits

In our proof we developed this algorithms for constructing a Euler

circuit in a graph with no vertices of odd degree.
 Applications of Euler Paths and
Circuits
• Euler paths and circuits can be used to solve many
practical problems such as finding a path or circuit that
traverses each
• street in a neighborhood,
• road in a transportation network,
• connection in a utility grid,
• link in a communications network.

• Other applications are found in the

• layout of circuits,
• network multicasting,
• molecular biology, where Euler paths are used in the sequencing
of DNA.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Necessary and Sufficient
Conditions for Euler Circuits and
Paths (continued)
Theorem: A connected multigraph with at least two vertices has an Euler circuit if
and only if each of its vertices has an even degree and it has an Euler path if and only
if it has exactly two vertices of odd degree.
Example: Two of the vertices in the multigraph model of the Kӧnigsberg bridge
problem have odd degree. Hence, there is no Euler circuit in this multigraph and it
is impossible to start at a given point, cross each bridge exactly once, and return to
the starting point.
Understanding Mohammed’s Scimitars.
Fleury’s Algorithm for printing Eulerian Path or Circuit
Eulerian Path is a path in a graph that visits every edge exactly once. Eulerian Circuit is an
Eulerian Path that starts and ends on the same vertex.

Following is Fleury’s Algorithm for printing the Eulerian trail or cycle

• Make sure the graph has either 0 or 2 odd vertices.

• If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start at one of
them.
• Follow edges one at a time. If you have a choice between a bridge and a non-bridge,
always choose the non-bridge.
• Stop when you run out of edges.
The idea is, “don’t burn bridges“ so that we can come back to a vertex and traverse the
remaining edges. For example, let us consider the following graph.
 Hamilton Paths and
Circuits William Rowan

(1805- 1865)
Hamilton
Euler paths and circuits contained every edge only once.
Now we look at paths and circuits that contain every vertex exactly once.

William Hamilton invented the Icosian puzzle in 1857. It consisted of a wooden

dodecahedron (with 12 regular pentagons as faces), illustrated in
(a), with a peg at each vertex, labeled with the names of different cities. String was
used to used to plot a circuit visiting 20 cities exactly once. The graph form of the
puzzle is given in (b).

The solution (a Hamilton circuit) is given here.

 Hamilton Paths and Circuits

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, a simple path x0, x1, …, xn-1, xn in the graph G = (V, E) is
called a Hamilton path if V = {x0, x1, … , xn-1, xn } and xi ≠ xj for 0≤
i < j ≤ n, and the simple circuit x0, x1, …, xn-1, xn, x0
(with n > 0) is a Hamilton circuit if x0, x1, … , xn-1, xn is a Hamilton
path.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Hamilton Paths and Circuits

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Hamilton Paths and Circuits

Example: Which of these simple graphs has a Hamilton circuit or, if not, a
Hamilton path?

Solution:
G1 does not have a Hamilton circuit (Why?), but does have
a Hamilton path : a, b ,e , c, d.
G2 has a Hamilton circuit: a, b, c, d, e, a.
G3 has a Hamilton circuit: a,b,e,d,c,a

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Necessary Conditions for
Hamilton Circuits
Gabriel Andrew
Dirac
• Unlike for an Euler circuit, no simple necessary and sufficient
(1925-1984)
conditions are known for the existence of a Hamiton circuit.
• However, there are some useful necessary conditions. We describe

Dirac’s Theorem: If G is a simple graph with n ≥ 3 vertices such that

two of these now.

the degree of every vertex in G is ≥ n/2, then G has a Hamilton

circuit.

Ore’s Theorem: If G is a simple graph with n ≥ 3 vertices such that

deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices, then G has
a Hamilton circuit.
Øysten Ore

1968)
(1899-
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Applications of Hamilton Paths and Circuits

• Applications that ask for a path or a circuit that visits each

intersection of a city, each place pipelines intersect in a utility grid,
or each node in a communications network exactly once, can be
solved by finding a Hamilton path in the appropriate graph.

• The famous traveling salesperson problem (TSP) asks for the

shortest route a traveling salesperson should take to visit a set of
cities. This problem reduces to finding a Hamilton circuit such that
the total sum of the weights of its edges is as small as possible.

• A family of binary codes, known as Gray codes, which minimize

the effect of transmission errors, correspond to Hamilton circuits
in the n-cube Qn.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
ISOMORPHISM OF
GRAPHS
Section 10.3
 Isomorphism of Graphs
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2)
are isomorphic if there is a one-to-one and onto function f
from V1 to V2 with the property that a and b are adjacent in
G1 if and only if f(a) and f(b) are adjacent in G2 , for all a and
b in V1 . Such a function f is called an isomorphism. Two
simple graphs that are not isomorphic are called
nonisomorphic.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Isomorphism of Graphs
• It is difficult to determine whether two simple graphs are
isomorphic using brute force because there are n! possible
one-to-one correspondences between the vertex sets of
two simple graphs with n vertices.

• The best algorithms for determining weather two graphs

are isomorphic have exponential worst case complexity in
terms of the number of vertices of the graphs.

• Sometimes it is not hard to show that two graphs are not

isomorphic. We can do so by finding a property, preserved
by isomorphism, that only one of the two graphs has. Such
a property is called graph invariant.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Isomorphism of Graphs

• Number of Vertices
• Number of Edges
• Degree of Sequence
• Mapping

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Isomorphism of Graphs (cont.)
Example: Show that the graphs G =(V, E) and H = (W, F) are isomorphic.

Solution: The function f with

f(u1) = v1,f(u2) = v4, f(u3) = v3, and f(u4) = v2 is a one-to-one
correspondence between V and W.

Note that adjacent vertices in G are

u1 and u2, u1 and u3, u2 and u4,
and u3 and u4. Each of the pairs

f(u1) = v1 and f(u2) = v4, f(u1) = v1

and f(u3) = v3 , f(u2) = v4 and
f(u4) = v2 , and f(u3) = v3 and
f(u4) = v2 consists of two adjacent vertices in H.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Isomorphism of Graphs
Example: Show that the graphs G =(V, E) and G’ = (W,
F) are isomorphic.

Solution: The function f with

f(v1) = v1,f(v2) = v3, f(v3) = v5, f(v4) = v2 and f(v5) = v4
is a one-to-one correspondence between V and W.
Note that adjacent vertices in G are v1 and v2, v2 and
v3, v3 and v4, v4 and v5 and v5 and v1.
Each of the pairs f(v1) = v1 and f(v2) = v3, f(v2) = v3
and f(v3) = v5 , f(v3) = v5 and
f(v4) = v2 , f(v4) = v2 and f(v5) = v4 and f(v5) = v4 and
f(v1) = v1 consists of two adjacent vertices in H.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Isomorphism of Graphs

EXAMPLE: Determine whether the graph G and G’ given below are

isomorphic.

SOLUTION:
As both the graphs have the same number of vertices. But the graph G has 7
edges and the graph G’ has only 6 edges. Therefore the two graphs are not
isomorphic.
Note: As the edges of both the graphs G and G’ are not same then how the
one-one correspondence is possible ,that the reason the graphs G and G’ are
not isomorphic.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Isomorphism of Graphs
EXAMPLE: Determine whether the graph G and G’ given below are
isomorphic.

SOLUTION:
Both the graphs have 5 vertices and 7 edges. The vertex q of G’ has degree
5. However G does not have any vertex of degree 5 (so one-one
correspondence is not possible). Hence, the two graphs are not isomorphic.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Isomorphism of Graphs
EXAMPLE: Determine whether the graph G and G’ given below are
isomorphic.

SOLUTION:
Clearly the vertices of both the graphs G and G’ have the same degree (i.e “2”)
and having the same number of vertices and edges but isomorphism is not
possible. As the graph G’ is a connected graph but the graph G is not
connected due to have two components (eca and bdf). Therefore the two
graphs are non isomorphic.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Isomorphism of Graphs
EXAMPLE: Determine whether the graph G and G’ given below are isomorphic.

SOLUTION:
Clearly G has six vertices, G’ also has six vertices. And the graph G has two
simple circuits of length 3; one is abca and the other is defd. But G’ does not
have any simple circuit of length 3(as one simple circuit in G’ is uxwvu of length
4).Therefore the two graphs are non-isomorphic.
Note: A simple circuit is a circuit that does not have any other repeated vertex
except the first and last.
 Isomorphism of Graphs
EXAMPLE: Determine whether the graph G and G’ given below are isomorphic.

SOLUTION:
Both the graph G and G’ have 8 vertices and 12 edges and both are also called
regular graph(as each vertex has degree 3).The graph G has two simple circuits
of length 5; abcfea(i.e starts and ends at a) and cdhgfc(i.e starts and ends at c).
But G’ does not have any simple circuit of length 5 (it has simple circuit
tyxut,vwxuv of length 4 etc). Therefore the two graphs are non-isomorphic.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Isomorphism of Graphs
EXAMPLE: Determine whether the given graph G and
H are isomorphic.
Solution:
Solution: The function f with
f(a) = u, f(b) = v, f(c) = y, f(d) = x, f(e) = w and f(f) = z is a
one-to-one correspondence between G and H.

Note that adjacent vertices in G are a and b, b and c, c

and d, c and f, d and e, e and f and f and a.

Each of the pairs f(a) = u and f(b) = v, f(b) = v and f(c) =

y , f(c) = y and f(d) = x , f(c) = y and f(f) = z , f(d) = x and
f(e) = w, f(e) = w and f(f) = z and f(f) = z and f(a) = u
consists of two adjacent vertices in H.
 Algorithms for Graph Isomorphism

• The best algorithms known for determining whether two graphs are
isomorphic have exponential worst-case time complexity (in the
number of vertices of the graphs).

• However, there are algorithms with linear average-case time

complexity.

• You can use a public domain program called NAUTY to determine in

less than a second whether two graphs with as many as 100
vertices are isomoprhic.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Applications of Graph
Isomorphism
• The question whether graphs are isomorphic plays an important
role in applications of graph theory. For example,

• chemists use molecular graphs to model chemical compounds. Vertices

represent atoms and edges represent chemical bonds. When a new
compound is synthesized, a database of molecular graphs is checked to
determine whether the graph representing the new compound is isomorphic
to the graph of a compound that this already known.
• Electronic circuits are modeled as graphs in which the vertices represent
components and the edges represent connections between them. Graph
isomorphism is the basis for

• the verification that a particular layout of a circuit

corresponds to the design’s original schematics.
• determining whether a chip from one vendor
includes the intellectual property of another vendor.
 10.6
Shortest-Path Problems
 Weighted Graphs
Graphs that have a number assigned to
each edge are called weighted graphs.
BOS

CHI NY
SF DEN

ATL
LA

MIA
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Weighted Graphs
MILES

BOS
2534 860

191
1855 722 NY
CHI
SF DEN 908
957
606

7 60
4
349 83

1090
2 45 1
ATL
LA 595
MIA
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Weighted Graphs
FARES

BOS
$129 $79
$39
$99 $59 NY
CHI
SF DEN $ 69
$89

$ 79

$ 99
$39 $89 $129
ATL
LA

$ 69
MIA
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Weighted Graphs
FLIGHT
TIMES

BOS
4:05
2:10
0:50
2:55 NY
CHI 1:50
SF DEN 2:10
2:20

1:55
1:4

2:45
0
1:15 2:00 3:50
ATL
LA

1:3
0
MIA
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Weighted Graphs
• A weighted graph is a graph in which each edge (u, v) has a weight w(u, v). Each
weight is a real number.

• Weights can represent distance, cost, time, capacity, etc.

• The length of a path in a weighted graph is the sum of the weights on the edges.

• Dijkstra vs Bellman Ford vs Floyd Warshall

• Dijkstra’s Algorithm finds the shortest path between two vertices.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Dijkstra’s Algorithm
• Dijkstra’s algorithm is used in problems relating to finding the shortest path.

• Each node is given a temporary label denoting the length of the shortest path
from the start node so far.

• This label is replaced if another shorter route is found.

• Once it is certain that no other shorter paths can be found, the temporary
label becomes a permanent label.

• Eventually all the nodes have permanent labels.

• At this point the shortest path is found by retracing the path backwards.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Dijkstra’s algorithm: example
D(v) D(w) D(x) D(y) D(z)
Step N'
0 u 7,u 3,u 5,u ∞ ∞
1 uw 6,w 5,u 11,w ∞
2 uwx 6,w 11,w 14,x
3 uwxv 10,v 14,x
4 uwxvy 12,y
5 uwxvyz x
9

notes: 5
4
7
 construct shortest path
8
tree by tracing
predecessor nodes u
3 w y z
 ties can exist (can be 2
broken arbitrarily) 3
7 4
v
 Dijkstra’s algorithm: another example

Step N' D(v) D(w) D(x) D(y) D(z)

0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz
5
3
v w 5
2
u 2 1 z
3
1 2
x 1
y

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Problem: shortest path from a to z

b 5 d 5 f
4 7
4 3 1
a 2 z
3 4
c 5 e 5 g

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 The Traveling Salesman Problem

•The traveling salesman problem is one of the classical problems in

computer science.
•A traveling salesman wants to visit a number of cities and then
return to his starting point. Of course he wants to save time and
energy, so he wants to determine the shortest cycle for his trip.
•We can represent the cities and the distances between them by a
weighted, complete, undirected graph.
•The problem then is to find the shortest cycle (of minimum total
weight that visits each vertex exactly one).
•Finding the shortest cycle is different than Dijkstra’s shortest path.
It is much harder too, no polynomial time algorithm exists!
 The Traveling Salesman Problem

• Importance:
• Variety of scheduling application can be solved as a
traveling salesmen problem.
• Examples:
• Ordering drill position on a drill press.
• School bus routing.
• The problem has theoretical importance because it
represents a class of difficult problems known as NP-hard
problems.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Travelling Salesman problem

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Travelling Salesman problem

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 10.7
Planar Graphs
The House-and-Utilities Problem
 Planar Graphs

•A graph is called planar if it can be drawn in

the plane without any edges crossing.
•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.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Example

A graph may be planar even if it is usually

drawn with crossings, since it may be
possible to draw it in another way without
crossings.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Example

A graph may be planar even if it represents a

3-dimensional object.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Planar Graphs

•We can prove that a particular graph is

planar by showing how it can be drawn
without any crossings.
•However, not all graphs are planar.
•It may be difficult to show that a graph is
nonplanar. We would have to show that
there is no way to draw the graph without
any edges crossing.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Regions
•Euler devised a formula for expressing the
relationship between the number of vertices,
edges, and regions of a planar graph.
•These may help us determine if a graph can
be planar or not.
 Euler’s Formula
•Let G be a connected planar simple graph
with e edges and v vertices. Let r be the
number of regions in a planar representation
of G. Then r = e - v + 2.

R4 R3 R2
# of edges, e = 6
R1 # of vertices, v = 4
# of regions, r = e - v + 2 = 4
 Euler’s Formula (Cont.)
•Corollary 1: If G is a connected planar
simple graph with e edges and v vertices
where v  3, then e  3v - 6.
•Is K5 planar?

K5
 Euler’s Formula (Cont.)
• K5 has 5 vertices and 10 edges.
• We see that v  3.
• So, if K5 is planar, it must be true that e  3v – 6.
• 3v – 6 = 3*5 – 6 = 15 – 6 = 9.
• So e must be  9.
• But e = 10.
• So, K5 is nonplanar.

K5
 Euler’s Formula (Cont.)
•Corollary 2: If G is a connected planar
simple graph, then G must have a vertex of
degree not exceeding 5.
If G has one or two vertices, it is true;
thus, we assume that G has at least three vertices.

If the degree of each vertex were at least 6, then by Handshaking Theorem,

2e ≥ 6v, i.e., e ≥ 3v,

but this contradicts the inequality from

Corollary 1: 1 e ≤ 3v – 6.
2e  deg( v )
vV
 Euler’s Formula (Cont.)
•Corollary 3: If a connected planar simple
graph has e edges and v vertices with v  3
and no circuits of length 3, then e  2v - 4.
•Is K3,3 planar?
 Euler’s Formula (Cont.)
• K3,3 has 6 vertices and 9 edges.
• Obviously, v  3 and there are no circuits of length 3.
• If K3,3 were planar, then e  2v – 4 would have to be true.
• 2v – 4 = 2*6 – 4 = 8
• So e must be  8.
• But e = 9.
• So K3,3 is nonplanar.

K3,3
 Kuratowski’s Theorem
We have seen that K3,3 and K5 are not planar. Clearly, a graph is
not planar if it contains either of these two graphs as a subgraph.
Surprisingly, all nonplanar graphs must contain a subgraph that
can be obtained from K3,3 or K5 using certain permitted
operations. If a graph is planar, so will be any graph obtained by
removing an edge {u, v} and adding a new vertex w together with
edges {u,w} and {w, v}. Such an operation is called an elementary
subdivision. The graphs G1 = (V1, E1) and G2 = (V2, E2) are called
homeomorphic if they can be obtained from the same graph by a
sequence of elementary subdivisions
10.8 Graph Coloring
10.8 Graph Coloring
 10.8 Graph Coloring
A 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.

The 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 χ (G).
(Here χ is the Greek letter chi.)
THEOREM 1

THE FOUR COLOR THEOREM The chromatic number of a

planar graph is no greater than four.
10.8 Graph Coloring
10.8 Graph Coloring
10.8 Graph Coloring
 Applications of Graph Colorings
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. A scheduling of the 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. In Figure 8 the graph associated with
this set of classes is shown. A 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. A coloring of the graph using four colors and the
associated schedule are shown in Figure 9.
Applications of Graph Colorings
Applications of Graph Colorings