29-01-2026

Chapter Summary
 Graphs and Graph Models
 Graph Terminology and Special Types of Graphs
 Representing Graphs and Graph Isomorphism
Chapter 10  Connectivity
 Euler and Hamiltonian Graphs
 Shortest-Path Problems (not currently included in
overheads)
 Planar Graphs (not currently included in overheads)
 Graph Coloring (not currently included in overheads)

Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.

Section Summary
 Introduction to Graphs
 Graph Taxonomy
 Graph Models
Section 10.1

Graphs Some Terminology

Definition: A graph G = (V, E) consists of a nonempty set V of vertices (or nodes) and a  In a simple graph each edge connects two different vertices and no two
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. edges connect the same pair of vertices.
 Multigraphs may have multiple edges connecting the same two
Example: a b
This is a graph
vertices. When m different edges connect the vertices u and v, we say
with four that {u,v} is an edge of multiplicity m.
vertices and five
edges.  An edge that connects a vertex to itself is called a loop.
d c  A pseudograph may include loops, as well as multiple edges connecting
the same pair of vertices.
Remarks:
 The graphs we study here are unrelated to graphs of functions studied in Chapter 2. Example: a b Remark: There is no standard
 We have a lot of freedom when we draw a picture of a graph. All that matters is the connections made by the This pseudograph terminology for graph theory. So, it is
edges, not the particular geometry depicted. For example, the lengths of edges, whether edges cross, how
vertices are depicted, and so on, do not matter has both multiple crucial that you understand the
 A graph with an infinite vertex set is called an infinite graph. A graph with a finite vertex set is called a finite edges and a loop. terminology being used whenever you
graph. We (following the text) restrict our attention to finite graphs.
read material about graphs.
c

1
 29-01-2026

Directed Graphs Some Terminology (continued)

Definition: An directed graph (or digraph) G = (V, E)  A simple directed graph has no loops and no multiple edges.
consists of a nonempty set V of vertices (or nodes) and Example: a b
a set E of directed edges (or arcs). Each edge is This is a directed graph with
associated with an ordered pair of vertices. The three vertices and four edges.
c
directed edge associated with the ordered pair (u,v) is  A directed multigraph may have multiple directed edges. When there
said to start at u and end at v. are m directed edges from the vertex u to the vertex v, we say that (u,v)
is an edge of multiplicity m.
Remark:
 Graphs where the end points of an edge are not ordered
Example:
are said to be undirected graphs. a b
In this directed multigraph the
multiplicity of (a,b) is 1 and the
multiplicity of (b,c) is 2.
c

Graph Models: Graph Models:

Computer Networks Computer Networks (continued)
 When we build a graph model, we use the appropriate type of graph to • To model a computer network
capture the important features of the application. where we care about the number
 We illustrate this process using graph models of different types of of links between data centers, we
computer networks. In all these graph models, the vertices represent use a multigraph.
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 • To model a computer network
simple graph. This is the appropriate type of graph when we only care with diagnostic links at data
whether two data centers are directly linked (and not how many links centers, we use a pseudograph,
there may be) and all communications links work in both directions. as loops are needed.

• 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 Terminology: Summary Other Applications of Graphs

 To understand the structure of a graph and to build a graph  We will illustrate how graph theory can be used in models
model, we ask these questions: of:
• Are the edges of the graph undirected or directed (or both)?  Social networks
• If the edges are undirected, are multiple edges present that  Communications networks
connect the same pair of vertices? If the edges are directed,  Information networks
are multiple directed edges present?  Software design
• Are loops present?
 Transportation networks
 Biological networks
 It’s a challenge to find a subject to which graph theory has
not yet been applied. Can you find an area without
applications of graph theory?

2
 29-01-2026

Graph Models: Social Networks

Graph Models: Social Networks (continued)
 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 Example: A friendship
organizations and edges represent relationships between graph where two people
them. are connected if they are
 Useful graph models of social networks include: Facebook friends.

 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 Example: An
people are connected if they collaborate in a specific way influence graph

 influence graphs - directed graphs where there is an edge

from one person to another if the first person can
influence the second person Next Slide: Collaboration Graphs

Examples of Collaboration Graphs Applications to Information Networks

 The Hollywood graph models the collaboration of actors in films.  Graphs can be used to model different types of networks
 We represent actors by vertices and we connect two vertices if the that link different types of information.
actors they represent have appeared in the same movie.  In a web graph, web pages are represented by vertices and
 We will study the Hollywood Graph in Section 10.4 when we links are represented by directed edges.
discuss Kevin Bacon numbers.
 A web graph models the web at a particular time.
 An academic collaboration graph models the collaboration of
researchers who have jointly written a paper in a particular  We will explain how the web graph is used by search engines
subject. in Section 11.4.
 We represent researchers in a particular academic discipline using  In a citation network:
vertices.  Research papers in a particular discipline are represented by
 We connect the vertices representing two researchers in this vertices.
discipline if they are coauthors of a paper.
 When a paper cites a second paper as a reference, there is an
 We will study the academic collaboration graph for mathematicians
when we discuss Erdős numbers in Section 10.4.
edge from the vertex representing this paper to the vertex
representing the second paper.

Transportation Graphs Software Design Applications

 Graph models are extensively used in the study of  Graph models are extensively used in software design. We will introduce two
such models here; one representing the dependency between the modules of a
transportation networks. software application and the other representing restrictions in the execution
of statements in computer programs.
 Airline networks can be modeled using directed  When a top-down approach is used to design software, the system is divided
multigraphs where into modules, each performing a specific task.
 airports are represented by vertices  We use a module dependency graph to represent the dependency between these
modules. These dependencies need to be understood before coding can be
 each flight is represented by a directed edge from the vertex done.
representing the departure airport to the vertex representing  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.
the destination airport
 Road networks can be modeled using graphs where
Example: The dependencies between the
 vertices represent intersections and edges represent roads. seven modules in the design of a web
browser are represented by this module
 undirected edges represent two-way roads and directed edges dependency graph.
represent one-way roads.

3
 29-01-2026

Software Design Applications

(continued) Biological Applications
 We can use a directed graph called a precedence graph to  Graph models are used extensively in many areas of the
represent which statements must have already been biological science. We will describe two such models, one
executed before we execute each statement. to ecology and the other to molecular biology.
 Vertices represent statements in a computer program  Niche overlap graphs model competition between species
 There is a directed edge from a vertex to a second vertex if the in an ecosystem
second vertex cannot be executed before the first
 Vertices represent species and an edge connects two vertices
Example: This precedence when they represent species who compete for food resources.
graph shows which statements
must already have been executed
before we can execute each of Example: This is the
the six statements in the niche overlap graph for
program. a forest ecosystem
with nine species.

Biological Applications (continued)

 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 Section 10.2
 Protein interaction graphs are often split into smaller graphs, called
modules, which represent the interactions between proteins involved
in a particular function.
Example: This is a module of
the protein interaction graph of
proteins that degrade RNA in a
human cell.

Section Summary Basic Terminology

 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
 Some Special Types of Graphs 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.
 Bipartite Graphs
 Bipartite Graphs and Matchings (not currently 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
included in overheads) of V, we denote by N(A) the set of all vertices in G that are
 Some Applications of Special Types of Graphs (not adjacent to at least one vertex in A. So,
currently included in overheads) Definition 3. The degree of a vertex in a undirected graph is the
 New Graphs from Old 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).

4
 29-01-2026

Degrees and Neighborhoods of

Vertices Degrees of Vertices
Example: What are the degrees and neighborhoods of the
vertices in the graphs G and H? Theorem 1 (Handshaking Theorem): If G = (V,E) is an undirected
graph with m edges, then

2𝑚 = deg(𝑣)
Solution: ∈

G: deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, Proof:

deg(e) = 3, deg(g) = 0. Each edge contributes twice to the degree count of all vertices. Hence,
N(a) = {b, f }, N(b) = {a, c, e, f }, N(c) = {b, d, e, f }, N(d) = {c}, both the left-hand and right-hand sides of this equation equal twice
N(e) = {b, c , f }, N(f) = {a, b, c, e}, N(g) =  . the number of edges.
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}, Think about the graph where vertices represent the people at a party and
N(d) = {a, b, e}, N(e) = {a, b ,d}. an edge connects two people who have shaken hands.

Handshaking Theorem Degree of Vertices (continued)

We now give two examples illustrating the usefulness of the Theorem 2: An undirected graph has an even number of
handshaking theorem. vertices of odd degree.
Proof: Let V1 be the vertices of even degree and V2 be the
Example: How many edges are there in a graph with 10 vertices
of degree six? vertices of odd degree in an undirected graph G = (V, E)
Solution: Because the sum of the degrees of the vertices is with m edges. Then
6  10 = 60, the handshaking theorem tells us that 2m = 60. even
So the number of edges m = 30.
This sum must be even because 2m
Example: If a graph has 5 vertices, can each vertex have degree must be is even and the sum of the degrees
3? even since of the vertices of even degrees is
Solution: This is not possible by the handshaking thorem, deg(v) is also even. Because this is the sum of
because the sum of the degrees of the vertices 3  5 = 15 is odd. even for the degrees of all vertices of odd
each v ∈ V1 degree in the graph, there must be
an even number of such vertices.

Directed Graphs Directed Graphs (continued)

Recall the definition of a directed graph. Definition: The in-degree of a vertex v, denoted
deg−(v), is the number of edges which terminate at v.
Definition: An directed graph G = (V, E) consists of V, The out-degree of v, denoted deg+(v), is the number of
a nonempty set of vertices (or nodes), and E, a set of edges with v as their initial vertex. Note that a loop at a
directed edges or arcs. Each edge is an ordered pair of
vertices. The directed edge (u,v) is said to start at u vertex contributes 1 to both the in-degree and the out-
and end at v. degree of the vertex.
Definition: Let (u,v) be an edge in G. Then u is the Example: In the graph G we have
initial vertex of this edge and is adjacent to v and v is deg−(a) = 2, deg−(b) = 2, deg−(c) = 3, deg−(d) = 2,
the terminal (or end) vertex of this edge and is adjacent deg−(e) = 3, deg−(f) = 0.
from u. The initial and terminal vertices of a loop are deg+(a) = 4, deg+(b) = 1, deg+(c) = 2, deg+(d) = 2,
the same. deg+ (e) = 3, deg+(f) = 0.

5
 29-01-2026

Special Types of Simple Graphs:

Directed Graphs (continued) Complete Graphs
Theorem 3: Let G = (V, E) be a graph with directed edges. A complete graph on n vertices, denoted by Kn, is the
Then: simple graph that contains exactly one edge between
each pair of distinct vertices.

Proof: The first sum counts the number of outgoing edges

over all vertices and the second sum counts the number of
incoming edges over all vertices. It follows that both sums
equal the number of edges in the graph.

Special Types of Simple Graphs: Special Types of Simple Graphs:

Cycles and Wheels n-Cubes
A cycle Cn for n ≥ 3 consists of n vertices v1, v2 ,⋯ , vn, An n-dimensional hypercube, or n-cube, Qn, is a graph
and edges {v1, v2}, {v2, v3} ,⋯ , {vn-1, vn}, {vn, v1}. 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.

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 Bipartite Graphs
Various special graphs play an important role in the design of computer networks. 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.

 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.
It is not hard to show that an equivalent definition of a bipartite
 Other local networks are based on a ring topology, where each device is connected to
graph is a graph where it is possible to color the vertices red or
exactly two others using Cn ,as illustrated in (b). Messages may be sent around the ring. blue so that no two adjacent vertices are the same color.
 Others, as illustrated in (c), use a Wn – based topology, combining the features of a star
topology and a ring topology.
 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. H is not bipartite
 The n-dimensional hypercube, or n-cube, Qn, is a common way to connect processors in G is since if we color a
parallel, e.g., Intel Hypercube. red, then the
 Another common method is the mesh network, illustrated here
bipartite
for 16 processors. adjacent vertices f
and b must both
be blue.

6
 29-01-2026

Bipartite Graphs (continued) Complete Bipartite Graphs

Example: Show that C6 is bipartite. Definition: A complete bipartite graph Km,n is a graph
Solution: We can partition the vertex set into that has its vertex set partitioned into two subsets
V1 = {v1, v3, v5} and V2 = {v2, v4, v6} so that every edge of C6
connects a vertex in V1 and V2 . 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

Example: Show that C3 is not bipartite.
Solution: If we divide the vertex set of C3 into two here.
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.

New Graphs from Old Bipartite Graphs and Matchings

Definition: A subgraph of a graph G = (V,E) is a graph (W,F), where W ⊂ V  Bipartite graphs are used to model applications that involve matching
and F ⊂ E. A subgraph H of G is a proper subgraph of G if H ≠ G. the elements of one set to elements in another, for example:
 Job assignments - vertices represent the jobs and the employees, edges
Example: Here we show K5 and link employees with those jobs they have been trained to do. A
one of its subgraphs. common goal is to match jobs to employees so that the most jobs are
done.

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.
 Marriage - vertices represent the men and the women and edges link a
Example: Here we show K5 and the subgraph a man and a woman if they are an acceptable spouse. We may wish to
induced by W = {a,b,c,e}. find the largest number of possible marriages.

See the text for more about matchings in bipartite graphs.

New Graphs from Old (continued)

Definition: The union of two simple graphs
G1 = (V1, E1) and G2 = (V2, E2) is the simple graph with
vertex set V1 ⋃ V2 and edge set E1 ⋃ E2. The union of
G1 and G2 is denoted by G1 ⋃ G2. Section 10.3

Example:

7
 29-01-2026

Representing Graphs:
Section Summary Adjacency Lists
 Adjacency Lists Definition: An adjacency list can be used to represent
 Adjacency Matrices a graph with no multiple edges by specifying the
 Incidence Matrices
vertices that are adjacent to each vertex of the graph.
Example:
 Isomorphism of Graphs

Example:

Representation of Graphs:
Adjacency Matrices Adjacency Matrices (continued)
Definition: Suppose that G = (V, E) is a simple graph Example: When a graph is sparse, that
where |V| = n. Arbitrarily list the vertices of G as is, it has few edges relatively
to the total number of
v1, v2, … , vn. The adjacency matrix AG of G, with possible edges, it is much
The ordering of
respect to the listing of vertices, is the n × n zero-one vertices is a, b, c, d.
more efficient to represent
the graph using an
matrix with 1 as its (i, j)th entry when vi and vj are adjacency list than an
adjacent, and 0 as its (i, j)th entry when they are not adjacency matrix. But for a
The ordering of dense graph, which includes
adjacent. a high percentage of
vertices is a, b, c, d.
 In other words, if the graphs adjacency matrix is possible edges, an adjacency
matrix is preferable.
AG = [aij], then
Note: The adjacency matrix of a simple graph is symmetric, i.e., aij = aji
Also, since there are no loops, each diagonal entry aij for i = 1, 2, 3, …, n, is 0.

Adjacency Matrices (continued) Adjacency Matrices (continued)

 Adjacency matrices can also be used to represent graphs with  Adjacency matrices can also be used to represent
loops and multiple edges.
 A loop at the vertex vi is represented by a 1 at the (i, j)th position
directed graphs. The matrix for a directed graph G =
of the matrix. (V, E) has a 1 in its (i, j)th position if there is an edge
 When multiple edges connect the same pair of vertices vi and vj, from vi to vj, where v1, v2, … vn is a list of the vertices.
(or if multiple loops are present at the same vertex), the (i, j)th  In other words, if the graphs adjacency matrix is AG = [aij], then
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.
 The adjacency matrix for a directed graph does not have to be
symmetric, because there may not be an edge from vi to vj, when
there is an edge from vj to vi.
 To represent directed multigraphs, the value of aij is the number
of edges connecting vi to vj.

8
 29-01-2026

Representation of Graphs:
Incidence Matrices Incidence Matrices (continued)
Definition: Let G = (V, E) be an undirected graph Example: Simple Graph and Incidence Matrix
with vertices where v1, v2, … vn and edges The rows going from top to
bottom represent v1 through
e1, e2, … em. The incidence matrix with respect to the v5 and the columns going
ordering of V and E is the n × m matrix M = [mij], from left to right represent e1
where through e6.

Example: Pseudograph and Incidence Matrix

The rows going from top to

bottom represent v1 through
v5 and the columns going
from left to right represent e1
through e8.

Isomorphism of Graphs Isomorphism of Graphs (cont.)

Definition: The simple graphs G1 = (V1, E1) and Example: Show that the graphs G =(V, E) and
G2 = (V2, E2) are isomorphic if there is a one-to-one H = (W, F) are isomorphic.
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 Solution: The function f with f(u1) = v1,
f(b) are adjacent in G2 , for all a and b in V1 . Such a f(u2) = v4, f(u3) = v3, and f(u4) = v2 is a
function f is called an isomorphism. Two simple graphs one-to-one correspondence between V and W.
Note that adjacent vertices in G are u1 and u2, u1 and
that are not isomorphic are called nonisomorphic. 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.

Isomorphism of Graphs (cont.) Isomorphism of Graphs (cont.)

 It is difficult to determine whether two simple graphs are isomorphic Example: Determine whether these two graphs
using brute force because there are n! possible one-to-one are isomorphic.
correspondences between the vertex sets of two simple graphs with n
vertices.
 The best algorithms for determining weather two graphs are Solution: Both graphs have eight vertices and ten edges.
isomorphic have exponential worst case complexity in terms of the They also both have four vertices of degree two and four of degree three.
number of vertices of the graphs. However, G and H are not isomorphic. Note that since deg(a) = 2 in G, a must
 Sometimes it is not hard to show that two graphs are not isomorphic. correspond to t, u, x, or y in H, because these are the vertices of degree 2. But
We can do so by finding a property, preserved by isomorphism, that each of these vertices is adjacent to another vertex of degree two in H, which is
only one of the two graphs has. Such a property is called graph not true for a in G.
invariant.
Alternatively, note that the subgraphs of G and H made up of vertices of
 There are many different useful graph invariants that can be used to degree three and the edges connecting them must be isomorphic.
distinguish nonisomorphic graphs, such as the number of vertices, But the subgraphs, as shown at the right, are not isomorphic.
number of edges, and degree sequence (list of the degrees of the
vertices in nonincreasing order). We will encounter others in later
sections of this chapter.

9
 29-01-2026

Isomorphism of Graphs (cont.) Algorithms for Graph Isomorphism

Example: Determine whether these two graphs
are isomorphic.  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).
Solution: Both graphs have six vertices and seven edges.
They also both have four vertices of degree two and two of degree three.  However, there are algorithms with linear average-case
The subgraphs of G and H consisting of all the vertices of degree two and the edges
connecting them are isomorphic. So, it is reasonable to try to find an isomorphism f. time complexity.
We define an injection f from the vertices of G to the vertices of H that preserves the  You can use a public domain program called NAUTY to
degree of vertices. We will determine whether it is an isomorphism.
determine in less than a second whether two graphs with as
The function f with f(u1) = v6, f(u2) = v3, f(u3) = v4, and f(u4) = v5 , f(u5) = v1, and f(u6) =
v2 is a one-to-one correspondence between G and H. Showing that this correspondence
many as 100 vertices are isomoprhic.
preserves edges is straightforward, so we will omit the details here. Because f is an
isomorphism, it follows that G and H are isomorphic graphs.  Graph isomorphism is a problem of special interest
See the text for an illustration of how adjacency matrices can be used for this verification.
because it is one of a few NP problems not known to be
either tractable or NP-complete (see Section 3.3).

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 Section 10.4
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.

Section Summary Paths

 Paths Informal Definition: A path is a sequence of edges
 Connectedness in Undirected Graphs
that begins at a vertex of a graph and travels from
vertex to vertex along edges of the graph. As the path
 Vertex Connectivity and Edge Connectivity (not travels along its edges, it visits the vertices along this
currently included in overheads) path, that is, the endpoints of these.
 Connectedness in Directed Graphs Applications: Numerous problems can be modeled
 Paths and Isomorphism (not currently included in with paths formed by traveling along edges of graphs
overheads) such as:
 determining whether a message can be sent between
 Counting Paths between Vertices two computers.
 efficiently planning routes for mail delivery.

10
 29-01-2026

Paths Paths (continued)

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 Example: In the simple graph here:
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.  a, d, c, f, e is a simple path of length 4.
 When the graph is simple, we denote this path by its vertex sequence  d, e, c, a is not a path because e is not connected to c.
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  b, c, f, e, b is a circuit of length 4.
has length greater than zero.
 The path or circuit is said to pass through the vertices x1, x2, … , xn-1  a, b, e, d, a, b is a path of length 5, but it is not a simple
and traverse the edges e1, … , en.
 A path or circuit is simple if it does not contain the same edge more
path.
than once.

This terminology is readily extended

to directed graphs. (see text)

Degrees of Separation Erdős numbers Paul Erdős

Example: Paths in Acquaintanceship Graphs. In an Example: Erdős numbers.

acquaintanceship graph there is a path between two In a collaboration graph, two people a and b are
connected by a path when there is a sequence
people if there is a chain of people linking these of people starting with a and ending with b
people, where two people adjacent in the chain know such that the endpoints of each edge in the
one another. In this graph there is a chain of six people path are people who have collaborated.
linking Kamini and Ching.  In the academic collaboration graph of people who have
written papers in mathematics, the Erdős number of a
Some have speculated that almost person m is the length of the shortest path between m
every pair of people in the world and the prolific mathematician Paul Erdős.
are linked by a small chain of no
more than six, or maybe even, five
 To learn more about Erdős numbers, visit
people. The play Six Degrees of [Link]
Separation by John Guare is based
on this notion.

Connectedness in Undirected
Bacon Numbrers Graphs
 In the Hollywood graph, two actors Definition: An undirected graph is called connected if
a and b are linked when there is a there is a path between every pair of vertices. An
chain of actors linking a and b, where undirected graph that is not connected is called
every two actors adjacent in the chain have disconnected. We say that we disconnect a graph when we
acted in the same movie. remove vertices or edges, or both, to produce a
 The Bacon number of an actor c is defined to be the disconnected subgraph.
length of the shortest path connecting c and the well- Example: G1 is connected because there is a path between
known actor Kevin Bacon. (Note that we can define a any pair of its vertices, as can be easily seen. However G2 is
similar number by replacing Kevin Bacon by a different not connected because there is no path between vertices a
actor.) and f, for example.
 The oracle of Bacon web site
[Link] provides a tool for
finding Bacon numbers.

11
 29-01-2026

Connected Components Connectedness in Directed Graphs

Definition: A connected component of a graph G is a Definition: A directed graph is strongly connected if
connected subgraph of G that is not a proper subgraph of there is a path from a to b and a path from b to a
another connected subgraph of G. A graph G that is not
connected has two or more connected components that are whenever a and b are vertices in the graph.
disjoint and have G as their union. Definition: A directed graph is weakly connected if
Example: The graph H is the union of three disjoint there is a path between every two vertices in the
subgraphs H1, H2, and H3, none of which are proper underlying undirected graph, which is the undirected
subgraphs of a larger connected subgraph of [Link] three graph obtained by ignoring the directions of the edges
subgraphs are the connected components of H.
of the directed graph.

Connectedness in Directed Graphs The Connected Components of the

(continued) Web Graph
Example: G is strongly connected
because there is a path between any  Recall that at any particular instant the web graph provides a snapshot of the
two vertices in the directed graph. web, where vertices represent web pages and edges represent links. According
Hence, G is also weakly connected. to a 1999 study, the Web graph at that time had over 200 million vertices and
The graph H is not strongly connected, since there is no directed path over 1.5 billion edges. (The numbers today are several orders of magnitude
from a to b, but it is weakly connected. larger.)
 The underlying undirected graph of this Web graph has a connected
component that includes approximately 90% of the vertices.
Definition: The subgraphs of a directed graph G that are strongly  There is a giant strongly connected component (GSCC) consisting of more
connected but not contained in larger strongly connected subgraphs, than 53 million vertices. A Web page in this component can be reached by
that is, the maximal strongly connected subgraphs, are called the following links starting in any other page of the component. There are three
strongly connected components or strong components of G. other categories of pages with each having about 44 million vertices:
 pages that can be reached from a page in the GSCC, but do not link back.
Example (continued): The graph H has three strongly connected  pages that link back to the GSCC, but can not be reached by following links
from pages in the GSCC.
components, consisting of the vertex a; the vertex e; and the subgraph
 pages that cannot reach pages in the GSCC and can not be reached from pages
consisting of the vertices b, c, d and edges (b,c), (c,d), and (d,b). in the GSCC.

Counting Paths between Vertices

Counting Paths between Vertices (continued)
 We can use the adjacency matrix of a graph to find the number of paths between two Example: How many paths of length four are there from a to d
vertices in the graph.
in the graph G.
Theorem: Let G be a graph with adjacency matrix A with respect to the ordering adjacency
v1, … , vn of vertices (with directed or undirected edges, multiple edges and loops G A=
allowed). The number of different paths of length r from vi to vj, where r >0 is a positive matrix of G
integer, equals the (i,j)th entry of Ar.

Proof by mathematical induction:

Basis Step: By definition of the adjacency matrix, the number of paths from vi to vj of length 1 Solution: The adjacency matrix of G (ordering
is the (i,j)th entry of A. the vertices as a, b, c, d) is given above. Hence
Inductive Step: For the inductive hypothesis, we assume that that the (i,j)th entry of Ar is the
A4 =
number of different paths of length r from vi to vj. the number of paths of length four from a to d is
 Because Ar+1 = Ar A, the (i,j)th entry of Ar+1 equals bi1a1j + bi2a2j + ⋯ + binanj, where bik is
the (i,k)th entry of Ar. By the inductive hypothesis, bik is the number of paths of length r
the (1, 4)th entry of A . The eight paths are as:
4

from vi to vk. a, b, a, b, d a, b, a, c, d
 A path of length r + 1 from vi to vj is made up of a path of length r from vi to some vk , and a, b, d, b, d a, b, d, c, d
an edge from vk to vj. By the product rule for counting, the number of such paths is the
product of the number of paths of length r from vi to vk (i.e., bik ) and the number of edges a, c, a, b, d a, c, a, c, d
from from vk to vj (i.e, akj). The sum over all possible intermediate vertices vk is bi1a1j + a, c, d, b, d a, c, d, c, d
bi2a2j + ⋯ + binanj .

12
 29-01-2026

Section Summary
 Euler Paths and Circuits
 Hamilton Paths and Circuits
 Applications of Hamilton Circuits
Section 10.5

Euler Paths and Circuits Euler Paths and Circuits (continued)

 The town of Kӧnigsberg, Prussia (now Kalingrad, Russia) was divided Definition: An Euler circuit in a graph G is a simple circuit
into four sections by the branches of the Pregel river. In the 18th containing every edge of G. An Euler path in G is a simple path
century seven bridges connected these regions.
containing every edge of G.
 People wondered whether whether it was possible to follow a path that
crosses each bridge exactly once and returns to the starting point. Example: Which of the undirected graphs G1, G2, and G3 has a
 The Swiss mathematician Leonard Euler proved that no such path Euler circuit? Of those that do not, which has an Euler path?
exists. This result is often considered to be the first theorem ever
proved in graph theory.

Solution: The graph G1 has an Euler circuit (e.g., a, e, c, d, e, b,

Multigraph a). But, as can easily be verified by inspection, neither G2 nor G3
Model of the has an Euler circuit. Note that G3 has an Euler path (e.g., a, c, d,
Bridges of
Kӧnigsberg
e, b, d, a, b), but there is no Euler path in G2, which can be
The 7 Bridges of Kӧnigsberg verified by inspection.

Necessary Conditions for Euler Circuits Sufficient Conditions for Euler Circuits
and Paths and Paths
 An Euler circuit begins with a vertex a and continues with an edge Suppose that G is a connected multigraph with ≥ 2 vertices, all of even degree. Let x0 = a
incident with a, say {a, b}. The edge {a, b} contributes one to deg(a). be a vertex of even degree. Choose an edge {x0, x1} incident with a and proceed to build a
 Each time the circuit passes through a vertex it contributes two to the simple path {x0, x1}, {x1, x2}, …, {xn-1, xn} by adding edges one by one until another edge
can not be added.
vertex’s degree.
 Finally, the circuit terminates where it started, contributing one to
We illustrate this idea in the graph G here.
deg(a). Therefore deg(a) must be even.
We begin at a and choose the edges
 We conclude that the degree of every other vertex must also be even. {a, f}, {f, c}, {c, b}, and {b, a} in succession.
 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  The path begins at a with an edge of the form {a, x}; we show that it must terminate at a
degree. with an edge of the form {y, a}. Since each vertex has an even degree, there must be an
even number of edges incident with this vertex. Hence, every time we enter a vertex other
 In the next slide we will show that these necessary conditions are also than a, we can leave it. Therefore, the path can only end at a.
sufficient conditions.  If all of the edges have been used, an Euler circuit has been constructed. Otherwise,
consider the subgraph H obtained from G by deleting the edges already used.

In the example H consists of the

vertices c, d, e.

13
 29-01-2026

Sufficient Conditions for Euler Circuits Algorithm for Constructing an

and Paths (continued) Euler Circuits
In our proof we developed this algorithms for
constructing a Euler circuit in a graph with no vertices of
 Because G is connected, H must have at least one vertex in common with the circuit that
has been deleted. odd degree.
In the example, the vertex is c. procedure Euler(G: connected multigraph with all vertices of even degree)
circuit := a circuit in G beginning at an arbitrarily chosen vertex with edges
 Every vertex in H must have even degree because all the vertices in G have even degree
and for each vertex, pairs of edges incident with this vertex have been deleted. Beginning successively added to form a path that returns to this vertex.
with the shared vertex construct a path ending in the same vertex (as was done before). H := G with the edges of this circuit removed
Then splice this new circuit into the original circuit. while H has edges
In the example, we end up with the circuit a, f, subciruit := a circuit in H beginning at a vertex in H that also is
c, d, e, c, b, a. an endpoint of an edge in circuit.
 Continue this process until all edges have been used. This produces an Euler circuit. H := H with edges of subciruit and all isolated vertices removed
Since every edge is included and no edge is included more than once. circuit := circuit with subcircuit inserted at the appropriate vertex.
 Similar reasoning can be used to show that a graph with exactly two vertices of odd return circuit{circuit is an Euler circuit}
degree must have an Euler path connecting these two vertices of odd degree

Necessary and Sufficient Conditions for

Euler Circuits and Paths (continued) Euler Circuits and Paths
Theorem: A connected multigraph with at least two vertices
has an Euler circuit if and only if each of its vertices has an Example:
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 G1 contains exactly two vertices of odd degree (b and d). Hence it has
Kӧnigsberg bridge problem have odd degree. Hence, there is an Euler path, e.g., d, a, b, c, d, b.
no Euler circuit in this multigraph and it is impossible to
G2 has exactly two vertices of odd degree (b and d). Hence it has an
start at a given point, cross each bridge exactly once, and Euler path, e.g., b, a, g, f, e, d, c, g, b, c, f, d.
return to the starting point.
G3 has six vertices of odd degree. Hence, it does not have an Euler path.

William Rowan

Applications of Euler Paths and Hamilton

(1805- 1865)

Circuits Hamilton Paths and Circuits

Euler paths and circuits contained every edge only once. Now we look at paths and circuits that
 Euler paths and circuits can be used to solve many practical 
contain every vertex exactly once.
problems such as finding a path or circuit that traverses  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
each 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).
 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  The solution (a Hamilton circuit) is given here.

 layout of circuits,
 network multicasting,
 molecular biology, where Euler paths are used in the
sequencing of DNA.

14
 29-01-2026

Hamilton Paths and Circuits

Hamilton Paths and Circuits (continued)
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 Example: Which of these simple graphs has a
graph G that passes through every vertex exactly once is called a Hamilton circuit or, if not, a Hamilton path?
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 Solution: G1 has a Hamilton circuit: a, b, c, d, e, a.
circuit if x0, x1, … , xn-1, xn is a Hamilton path.
G2 does not have a Hamilton circuit (Why?), but does
have a Hamilton path : a, b, c, d.
G3 does not have a Hamilton circuit, or a Hamilton
path. Why?

Necessary Conditions for Applications of Hamilton Paths and

Hamilton Circuits Gabriel Andrew Dirac
(1925-1984)
Circuits
 Unlike for an Euler circuit, no simple necessary and sufficient  Applications that ask for a path or a circuit that visits each
conditions are known for the existence of a Hamiton circuit. intersection of a city, each place pipelines intersect in a
 However, there are some useful necessary conditions. We utility grid, or each node in a communications network
describe two of these now. exactly once, can be solved by finding a Hamilton path in
Dirac’s Theorem: If G is a simple graph with n ≥ 3 vertices such the appropriate graph.
that the degree of every vertex in G is ≥ n/2, then G has a  The famous traveling salesperson problem (TSP) asks for
Hamilton circuit. the shortest route a traveling salesperson should take to
visit a set of cities. This problem reduces to finding a
Ore’s Theorem: If G is a simple graph with n ≥ 3 vertices such Hamilton circuit such that the total sum of the weights of
that deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices, its edges is as small as possible.
then G has a Hamilton circuit.  A family of binary codes, known as Gray codes, which
Øysten Ore minimize the effect of transmission errors, correspond to
(1899-1968) Hamilton circuits in the n-cube Qn. (See the text for
details.)

15