Graph Theory

Introduction to Graph Theory

• What is Graph Theory?
• Study of graphs which are mathematical structures
• Graph consists of vertices and edges which connects the vertices
• Where we are using Graph Theory?
Introduction to Graph Theory
• Where in computer science, we are using Graph Theory?
Introduction to Graph Theory
• Graphs can be used to
• Determine whether it is possible to walk down all the streets in a city without going
down a street twice.
• Design a circuit
• Determine a shortest route to travel
Graph Theory
• What is Graph?
• A graph is G=(V,E) consists of V, a non empty set of vertices (or nodes) and E, a set of
edges.
• Each edge is either one or two vertices associated with it, called as endpoints.
• An edge is said to be connected to the endpoints.
• A graph with infinite vertex set is called as an infinite graph
• A graph with a finite vertex set is called as a finite graph.

• Note that
• Each edge of the graph representing this computer network connects
two different vertices. That is, no edge connects a vertex to itself.
• No two different edges connect the same pair of vertices.
Types of Graphs
• Simple Graph
• A graph in which each edge connects two different vertices and where no two edges a
connect the same pair of vertices.
b
• Each edge is associated to an unordered pair of vertices, and no other edge is
associated to this same edge.
c
• Edge connecting to vertex a and vertex b (i.e. {a,b}) no other edge is associated to edge
{a,b} Simple graph

• Multigraph
• A graph in which multiple edges connects to the same pair of vertices.
• When there are m different edges associated to the same unordered pair of b
vertices {a,b}, we say that {a,b} is an edge of multiplicity m. a
• This set of edges connecting to a and b are m different copies of an edge {a,b} c
• Pseudograph Multigraph
• Loops: the edges that connect a vertex itself
• A graph containing loops and multiple edges connecting the same pair of
vertices are sometimes called as pseudograph.

Pseudograph
Types of Graphs
• Undirected Graphs
• A graph containing undirected edges.
• Directed Graphs(Diagraph)
• A graph (V,E) consists of a non-empty 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 (a,b) is said to start at a
and end at b.
• An arrow pointing from a to b indicate the direction of an edge that starts at
a and ends at b.

• Can have loops and may also contain multiple directed edges starting and
ending at same vertices.
• May contain directed edges that connect vertices a and b in both directions
Types of Graphs
• Directed Graphs(Diagraph) a b
• A directed graph with no loops and has no multiple directed edges from a
and b is called as simple directed graph.
• Has at most one edge associated to each ordered pair of vertices
• Directed graphs that may have multiple directed edges from a vertex to a c
second (possibly the same) vertex is called as directed multigraphs.
• When there are m directed edges, each associated to an ordered pair of vertices
(a, b), we say that (a, b) is an edge of multiplicity m.

• Mixed Graph
• A graph with both directed and undirected edges is called a mixed graph.
• Used to model a computer network containing links that operate in both
directions and other links that operate only in one direction.
Types of Graphs

Table: Graph Terminology

Type Edges Multiple edges allowed? Loops allowed?

Simple graph Undirected No No

Multigraph Undirected Yes No
Pseudograph Undirected Yes Yes
Simple directed graph Directed No No
Directed multigraph Directed Yes Yes
Mixed graph Directed or undirected Yes Yes
 Types of Graphs
1
A B a
2 5
b
D C c f
3 4
Simple directed graph e

Directed multigraph d
Multigraph
Graph Terminologies of Undirected Graph
• Two vertices u and v in an undirected graph G are called adjacent (or neighbours) in G if u
and v are endpoints of an edge of G.
• If edge e is associated with {u,v}, the edge e is called incident with the vertices u and v.
• The edge e is said to connect u and v
• The vertices u and v are called as endpoints of an edge associated with {u,v }.
• The degree of vertex in an undirected graph is the number of edges incident with it, except
that a loop at a vertex contributes twice to the degree of that vertex.
• The degree of vertex is denoted by deg(v).
a What is the degree of vertex
1. a  4
b 2. b  5
c f 3. c  2
4. d  2
e
5. e  3
d 6. f  2
Graph Terminologies of Undirected Graph
• A vertex of degree zero is called isolated.
• Such isolated vertex is not adjacent to any vertex.
• A vertex is a pendant if and only if it has degree one.
• A pendant vertex is adjacent to one and only one other vertex.
Graph Terminologies of Undirected Graph
• The Handshaking Theorem
Let G = (V, E) be an undirected graph with e edges. Then

2𝑒 = deg(𝑣)
𝑣∈𝑉

This applies even if multiple edges and loops are present in the graph.

Q. How many edges are there in a graph with 12 vertices each of degree six?
Graph Terminologies of Undirected Graph
• In any undirected graph, the number of vertices that have an odd degree is
always even.
Proof
Let 𝑉1 and 𝑉2 be the set of vertices of even degree and set of vertices of odd degree
respectively, in an undirected graph. Then
2𝑒 = deg(𝑣) = deg(𝑣) + deg(𝑣)
𝑣∈𝑉 𝑣∈𝑉1 𝑣∈𝑉2

H
A C E

G
D

B F
Graph Terminologies of Directed Graph
• 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 as initial vertex of (u,v), and v is called as terminal
or end vertex of (u,v).
• The initial vertex and terminal vertex of a loop are the same. 1

2 5
• In a graph with directed edges
• The in-degree of a vertex v, denoted by deg 𝑣 is the number of edges
with v as their terminal vertex. 3 4
• The out-degree of a vertex v, denoted by deg+(v) is the number of edges
with v as their initial vertex.
• A loop at a vertex contributes 1 to both the in-degree and the out-degree
of this vertex.
Graph Terminologies of Directed Graph
Let G=(V,E) be a graph with directed edges. Then

+
𝑑𝑒𝑔 (𝑣) = 𝑑𝑒𝑔 𝑣 = 𝐸
𝑣∈𝑉 𝑣∈𝑉
Special Graph Terminologies
• Complete Graph
• The complete graph on n vertices, denoted by Kn, is the simple graph that contains
exactly one edge between each pair of distinct vertices.

• Cycles
• The cycle Cn, 𝑛 ≥ 3, consists of n vertices 𝑣1 , 𝑣2 , . . . , 𝑣𝑛 and edges {𝑣1 , 𝑣2 }, {𝑣2 , 𝑣3 },- ..
,{𝑣𝑛−1 , 𝑣𝑛 }, and {𝑣𝑛 , 𝑣1 }.
Special Graph Terminologies
• Wheels
• We obtain wheel Wn when we add an additional vertex to the cycle Cn, for 𝑛 ≥ 3, and
then we connect this new vertex to each of 𝒏 vertices in Cn by new edges.
Special Graph Terminologies
• n-Cube
• The n-dimensional hypercube, or n-cube, denoted by Qn, is the graph that has vertices
representing the 2n bit strings of length n.
• Two vertices are adjacent if and only if the bit strings that they represent differ in exactly
one bit position.
Graph Representations
• A graph G can be represented in two ways
• Adjacency matrix/list
• Useful when information about the vertices is more desirable than information of edges.

• Incidence matrix
• Useful when information about edges is more desirable than information of vertices

• Adjacency list/matrix is more commonly used representation.

Graph Representations
• Adjacency List
• It is way to represent a graph without multiple edges
• It specifies the vertices that are adjacent to each vertex of the graph.
Adjacency List of Undirected graph G
Vertex Adjacent vertices
a b, c, e
b a
c a, e, d
d c, e
e a, c, d
Graph Representations
• Adjacency List
Adjacency List of Directed graph G
Initial Vertex Terminal vertices
a b, c, d, e
b b, d
c a, c, e
d
e b, c, d
Graph Representations
• Determine the Adjacency List for following graphs

a b c

d e

a b d \

b a c d \

c b e \

d a b e \

e c d \
Graph Representations
• Determine the Adjacency List for following graphs

2 4
a b c

1 6

d e
3 5

a b d \ 1 2 \

b a c d \ 2 1 4 \

c b 3 1 2 5 \
e \
4 6 \
d a b e \
5 2 4 6 \
e c d \
6 \
Graph Representations
• Adjacency Matrix (simple graph)
• Suppose a graph G=(V,E) is a simple graph, where |V|=n
• Vertices are listed as v1, v2, . . ., vn
• Adjacency matrix A or (AG) of G, with respect to this listing of the vertices,is the 𝒏 × 𝒏
zero-one matrix with 1 as its (i,j)th entry when vi and vj are adjacent and 0 as its (i,j)th
entry when vi and vj are not adjacent.
• Or we can say adjacency matrix A =[aij], then
𝑛×𝑛
1 𝑖𝑓 𝑣𝑖 , 𝑣𝑗 𝑖𝑠 𝑎𝑛 𝑒𝑑𝑔𝑒 𝑜𝑓𝑔 a b c d
𝑎𝑖,𝑗 =
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 a 0 1 1 0
b 1 0 0 1
c 1 0 0 1
d 0 1 1 0
Graph Representations
• Adjacency Matrix (directed graph )
• Adjacency matrix A or (AG) of directed graph G, with respect to this listing of the vertices,is
the 𝒏 × 𝒏 zero-one matrix with 1 in its (i,j)th entry if there is an edge from vi and vj ,
• we can say adjacency matrix A =[aij] of directed graph w.r.t to the listing of the vertices,
then

1 𝑖𝑓 𝑣𝑖 , 𝑣𝑗 𝑖𝑠 𝑎𝑛 𝑒𝑑𝑔𝑒 𝑜𝑓𝑔
𝑎𝑖,𝑗 =
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

The adjacency matrix for a directed graph does not have to be symmetric, because there
may not be an edge from aj to ai when there is an edge from ai to aj.
Graph Representations
Graph Representations
• Determine the adjacency matrices for the following graphs
2 4
a b c

1 6

d e
3 5

a b c d e 1 2 3 4 5 6
a 0 1 0 1 0 1 0 1 0 0 0 0
b 1 0 1 1 0 a b c d
2 1 0 0 1 0 0
c 0 1 0 0 1 a 0 3 0 2
3 1 1 0 0 1 0
d 1 1 0 0 1 b
4 0 0 0 0 0 1 3 0 1 1
e 0 0 1 1 0 c 0 1 1 2
5 0 1 0 1 0 1
6 0 0 0 0 0 0 d 2 1 2 0
Graph Representations
• Incidence Matrix
• Let G=(V,E) is an undirected graph,
• Suppose 𝑣1 , 𝑣2 , . . . , 𝑣𝑛 are the vertices and 𝑒1 , 𝑒2 , . . . , 𝑒𝑚 are the edges of G.
• The incidence matrix w.r.t. this ordering of V and E is the 𝒏 × 𝒎 matrix 𝑀 = 𝑚𝑖𝑗 ,
where
1 𝑤ℎ𝑒𝑛 𝑒𝑑𝑔𝑒 𝑒𝑗 𝑖𝑠 𝑖𝑛𝑐𝑖𝑑𝑒𝑛𝑡 𝑤𝑖𝑡ℎ 𝑣𝑖
𝑚𝑖𝑗 =
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

v1 v2 e6 v3
e1 e2 e3 e4 e5 e6
e3 v1 1 1 0 0 0 0
v2 0 0 1 1 0 1
e1 e4 e5 v3 0 0 0 0 1 1
e2 v4 1 0 1 0 0 0
v5 0 1 0 1 1 0
v4 v5
𝑛×𝑚
Graph Representations
• Represent the following pseudograph using Incidence Matrix
e2
v1 v2 e4 v3
e1

e3 e6 e1 e2 e3 e4 e5 e6 e7 e8 e9
e5 v1 1 1 1 0 0 0 0 0 0
e8
v2 0 1 1 1 0 1 0 1 0
e7 v3 0 0 0 1 1 0 1 0 0
v4 v5 v4 0 0 0 0 0 0 1 1 1
e9 v5 0 0 0 0 1 1 0 0 0
Graph Representations
• Represent the following graph using Adjacency Matrix
Sub Graph
• Sometime we need only part of graph to solve a problem.
• When edges and vertices are removed from a graph, without removing
endpoints of any remaining edges, a smaller graph is obtained. Such a
graph is called a subgraph of the original graph.
• A subgraph of a graph 𝐺 = (𝑉, 𝐸) is a graph 𝐻 = (𝑊, 𝐹), where 𝑊 ⊆ 𝑉
and 𝐹 ⊆ 𝐸.
• A subgraph H of G is a proper subgraph of G if 𝐻 ≠ 𝐺
a b c a b

d e
d
Operations on Graphs
• Various operations can be performed on graphs
• Union (𝐴 ∪ 𝐵)
𝐴 = 2, 4, 6, 8, 10
𝐵 = 4, 8,12, 16
𝑨 ∪ 𝑩 = {𝟐, 𝟒, 𝟔, 𝟖, 𝟏𝟎, 𝟏𝟐, 𝟏𝟔}
• Intersection (𝐴 ∩ 𝐵)
𝐴 = 2, 4, 6, 8, 10
𝐵 = 4, 8,12, 16
𝑨 ∩ 𝑩 = {𝟒, 𝟖}
• Sum (𝐴 + 𝐵)
• Ring sum (𝐴⨁𝐵)
• Product (𝐴 × 𝐵)
Union of Graphs
• Two or more graphs can be combined in various ways. The new graph that contains all the
vertices and edges of these graphs is called the union of the graphs.
• The union of two simple graphs 𝐺1 = (𝑉1, 𝐸1) and 𝐺2 = (𝑉2, 𝐸2) is the simple graph
with vertex set 𝑽𝟏 ∪ 𝑽𝟐 and edge set 𝑬𝟏 ∪ 𝑬𝟐 . The union of 𝐺1 and 𝐺2 is denoted by
𝐺1 ∪ 𝐺2.
𝑉1 = 𝑎, 𝑏, 𝑐, 𝑑 , 𝑉2 = 𝑎, 𝑏, 𝑐, 𝑑, 𝑒
𝑽𝟏 ∪ 𝑽𝟐 = {𝒂, 𝒃, 𝒄, 𝒅, 𝒆}
𝐸1 = 𝑎, 𝑏 , 𝑎, 𝑑 , 𝑏, 𝑐 , 𝐸2 = 𝑎, 𝑑 , 𝑎, 𝑒 , 𝑏, 𝑑 , 𝑏, 𝑒 , 𝑐, 𝑒
𝑬𝟏 ∪ 𝑬𝟐 = { 𝒂, 𝒃 , 𝒂, 𝒅 , 𝒂, 𝒆 , 𝒃, 𝒄 , 𝒃, 𝒅 , 𝒃, 𝒆 , 𝒄, 𝒆 }
a b c a b c

d d
e
G1 G2
 Intersection of Graphs
• The intersection of two simple graphs 𝐺1 = (𝑉1, 𝐸1) and 𝐺2 = (𝑉2, 𝐸2) is the simple
graph with vertex set 𝑽𝟏 ∩ 𝑽𝟐 and edge set 𝑬𝟏 ∩ 𝑬𝟐 . The intersection of 𝐺1 and 𝐺2 is
denoted by 𝐺1 ∩ 𝐺2. Contains common vertices and common edges of these graphs.
𝑉1 = 1,2,3,4,5,6 , 𝑉2 = 1,2,3,4,5,6
𝑽𝟏 ∩ 𝑽𝟐 = {𝟏, 𝟐, 𝟑, 𝟒, 𝟓, 𝟔}
𝐸1 = 1,2 , 1,5 , 1,6 , 2,3 , 2,6 , 3,4 , 3,6 , 4,5 , 4,6 , 5,1 , {5,6}
𝐸2 = 1,6 , 2,6 , 3,6 , 4,6 , 5,6
𝑬𝟏 ∩ 𝑬𝟐 = { 1,6 , 2,6 , 3,6 , 4,6 , 5,6 } 1
1 1

5 2
5 2 5 2
G1
6 ∩ 6
6

4 3
G2
4 3 4 3 G1 ∩ G2
Sum of Graphs
• If two simple graphs 𝐺1 = (𝑉1, 𝐸1) and 𝐺2 = (𝑉2, 𝐸2), such that 𝑉1 ∩ 𝑉2 = ∅,
then the sum of 𝐺1 and 𝐺2 is denoted by 𝑮𝟏 + 𝑮𝟐 consists of those edges, which
are in G1 and in G2 and the edges obtained, by joining each vertex of G1 to each
vertex of G2.
𝑉1 = 𝑎, 𝑏 , 𝑉2 = 𝑥, 𝑦, 𝑧
𝑽𝟏 + 𝑽𝟐 = {𝒂, 𝒃, 𝒙, 𝒚, 𝒛}
𝐸1 = 𝑎, 𝑏 , 𝐸2 = { 𝑥, 𝑦 , 𝑦, 𝑧 }
𝑬𝟏 + 𝑬𝟐 = { 𝒂, 𝒃 , 𝒂, 𝒙 , 𝒂, 𝒚 , 𝒂, 𝒛 , 𝒃, 𝒙 , 𝒃, 𝒚 , 𝒃, 𝒛 , 𝒙, 𝒚 , {𝒚, 𝒛}}
x x
a a

+ y y

b b
G1 G2 z z
G1 + G2
Ring sum of Graphs
• The ring sum of two simple graphs 𝐺1 = (𝑉1, 𝐸1) and 𝐺2 = (𝑉2, 𝐸2) is the
simple graph with vertex set 𝑽𝟏 ∪ 𝑽𝟐 and the edges that are either in 𝐺1 or in
𝐺2 but not in both i.e. (𝑬𝟏 ∪ 𝑬𝟐) − (𝑬𝟏 ∩ 𝑬𝟐) . The ring sum of 𝐺1 and 𝐺2 is
denoted by 𝐺1⨁𝐺2.
𝑉1 = 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 , 𝑉2 = 𝑏, 𝑐, 𝑑, 𝑒
𝑽𝟏 ∪ 𝑽𝟐 = {𝒂, 𝒃, 𝒄, 𝒅, 𝒆}
𝐸1 = 𝑎, 𝑏 , 𝑎, 𝑐 , 𝑎, 𝑑 , 𝑎, 𝑒 , 𝑏, 𝑐 , 𝑏, 𝑑 , 𝑏, 𝑒 , 𝑐, 𝑑 , {𝑑, 𝑒}
𝐸2 = { 𝑏, 𝑐 , 𝑏, 𝑒 , 𝑐, 𝑑 , 𝑐, 𝑒 , {𝑑, 𝑒}}
(𝑬𝟏 ∪ 𝑬𝟐) − (𝑬𝟏 ∩ 𝑬𝟐) = { 𝒂, 𝒃 , 𝒂, 𝒄 , 𝒂, 𝒅 , 𝒂, 𝒆 , 𝒃, 𝒅 , {𝒄, 𝒆}}
a a

b e b e b e

⨁
c d c d c d
G1 G2 G1 ⨁ G2
Product of Graphs
• Product of sets A and B
𝐴 = 1, 2, 3, 4, 5 , 𝐵 = {9, 8, 7}
𝐴 × 𝐵 = { 1,9 , 1,8 , 1, 7 , 2,9 , 2, 8 , 2, 7 , . . . , 5, 9 , 5,8 , 5,7 }

• Product of graphs G and H

• Vertex set of G is 𝑉 𝐺 = {𝑣1 , 𝑣2 , . . . , 𝑣𝑛 }
• Vertex set of H is 𝑉 𝐻 = {𝑢1 , 𝑢2 , . . . , 𝑢𝑚 }

• Product of G and H i.e. V 𝐺 × 𝐻 = { 𝑣𝑖 , 𝑢𝑗 𝑣𝑖 ∈ 𝑉 𝐺 𝑎𝑛𝑑 𝑢𝑗 ∈ 𝑉(𝐻)}

𝑉 𝐺 × 𝐻 = { 𝑣1 , 𝑢1 , 𝑣1 , 𝑢2 , . . . , 𝑣1 , 𝑢𝑚 , 𝑣2 , 𝑢1 , 𝑣2 , 𝑢2 , . . . , 𝑣2 , 𝑢𝑚 , . . . , 𝑣𝑛 , 𝑢1 , 𝑣𝑛 , 𝑢2 , . . . , 𝑣𝑛 , 𝑢𝑚 }

• Two vertices 𝑣𝑖 , 𝑢𝑗 𝑎𝑛𝑑 𝑣𝑘 , 𝑢𝑙 are adjacent in 𝐺 × 𝐻 if and only if either

𝑣𝑖 = 𝑣𝑘 𝑎𝑛𝑑 𝑢𝑗 is adjacent to 𝑢𝑙 in H OR
𝑢𝑗 = 𝑢𝑙 𝑎𝑛𝑑 𝑣𝑖 is adjacent to 𝑣𝑘 in G
Product of Graphs
• Example (a,1)

a 1 (b,1) (c,1)
(a,2)
2 (b,2) (c,2)
(a,3)
3 (b,3) (c,3)
(a,4)
b c 4 (b,4) (c,4)
 Path
• 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.
• For a graph G=(V,E), a path of length 𝑛 from u to v in G is a sequence of n edges 𝑒1 , 𝑒2 , … , 𝑒𝑛 of
G such that 𝑒1 is associated with {𝑣0 , 𝑣1 }, 𝑒2 is associated with {𝑣1 , 𝑣2 }. and so on, with 𝑒𝑛
associated with {𝑣𝑛−1 , 𝑣𝑛 }, where 𝑣0 = u and 𝑣𝑛 = v.
• We denote the path by its vertex sequence 𝑣0 , 𝑣1 , . . . , 𝑣𝑛 because listing these vertices
uniquely determines the path.
• The path is a circuit if it begins and ends at the same vertex i.e., if u = v, and has length greater
than zero.
• The path or circuit is said to pass through the vertices 𝑣0 , 𝑣1 , . . . , 𝑣𝑛−1 or traverse the edges
𝑒1 , 𝑒2 , … , 𝑒𝑛 .
• A path or circuit is simple if it does not contain the same edge more than once.
Path

a,b,c,f,e,d is a simple path with length 5.

a,b,c,f,e,d,a is a circuit with length 6.
b,f,e,c,d is not a path.
a,e,f,e,b,c is not a simple path with length 4
because it contains {e,f} twice.
Graph Connectivity
• Connectivity defines whether a graph is connected or disconnected.
• An undirected graph is called connected if there is a path between every pair of
distinct vertices of the graph.
• From every vertex to any other vertex, there should be some path to traverse that is called
the connectivity of a graph.
• A graph with multiple disconnected vertices and edges is said to be
disconnected.

G1 G2 G3
Graph Connectivity
• A directed graph is strongly connected if there is a path from a to b and from b to
a whenever a and b are vertices in the graph.
• A directed graph is weakly connected if there is a path between every two
vertices in the underlying undirected graph.
• i.e. A directed graph is weakly connected if and only if there is always a path between two
vertices when the directions of the edges are disregarded.

G is strongly connected. H is weakly connected.

Euler and Hamiltonian Graphs
• Can we travel along the edges of a graph starting at a vertex and returning to it by traversing
each edge of the graph exactly once?

Euler Circuit

• Can we travel along the edges of a graph starting at a vertex and returning to it while visiting
each vertex of the graph exactly once?

Hamiltonian Circuit
Euler and Hamiltonian Graphs
• Euler Path and Circuit
• The town of Konigsberg, Prussia, was divided into four sections by the branches of the
Pregel River

• The townspeople wondered whether it was possible to start at some location in the town,
travel across all the bridges without crossing any bridge twice, and return to the starting
point.
• Swiss mathematician Leonhard Euler solved this problem using Graph theory
Euler and Hamiltonian Graphs
• Euler Circuit and Path
• 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.

G1has Euler circuit G2 has neither G3 doesn’t have Euler circuit

a, e, c, d, b, a Euler circuit nor but it has Euler path
Euler path a, c, d, e, b, d, a, b
 Euler and Hamiltonian Graphs

Which of the following directed graphs have an Euler circuit? Of those that do not, which have an Euler path?
Euler and Hamiltonian Graphs
• Necessary And Sufficient Conditions For Euler Circuits And Paths
• A connected multigraph with at least two vertices has an Euler circuit if and only if each
of its vertices has even degree a

b e Euler Circuit: a, c, e, a, b, d, a
deg(a)=4, deg(c)=2, deg(e)=2,
deg(b)=2, deg(d)=2
c d

• A connected multigraph has an Euler path but not an Euler circuit if and only if it has
exactly two vertices of odd degree.

Euler path: b, a, g, f, e, d, c, g, b, c, f, d
deg(a)=2, deg(b)=3, deg(c)=4,
deg(d)=3, deg(e)=2, deg(f)=4, deg(g)=4
Euler and Hamiltonian Graphs
• Hamilton Path and Circuit
• A simple path in a graph G that passes through every vertex exactly once is called a
Hamilton path.
• A simple circuit in a graph G that passes through every vertex exactly once is called a
Hamilton circuit.

Hamilton path:
Hamilton Circuit: a, b, d, c Neither Hamilton circuit nor
a, b, c, d, e, a a, b, c, d Hamilton path
Euler and Hamiltonian Graphs
• Hamilton Path and Circuit
• A graph with a vertex of degree one cannot have a Hamilton circuit,
• Because in a Hamilton circuit, each vertex is incident with two edges in the circuit.
• When a Hamilton circuit is being constructed and this circuit has already passed through
a vertex, then all remaining edges incident with this vertex, other than the two used
in the circuit, can be removed from consideration.
• A Hamilton circuit cannot contain a smaller circuit within it.
Euler and Hamiltonian Graphs
• Hamilton Path and Circuit
• 𝐾𝑛 has a Hamilton circuit whenever 𝑛 ≥ 3.

• If 𝐺 is a simple graph with 𝑛 vertices with 𝑛 ≥ 3 such that the degree of every vertex in
G is at least 𝒏 𝟐, then G has a Hamilton circuit.

• If is G a simple graph with n vertices with 𝑛 ≥ 3 such that 𝒅𝒆𝒈 𝒖 + 𝒅𝒆𝒈(𝒗) ≥ 𝒏 for
every pair of non-adjacent vertices u and v in G, then G has a Hamilton circuit.