CHAPTER 1 : DEFINITIONS AND FUNDAMENTAL CONCEPTS

Graph

Definition 1
A graph G = (V, E) consists of V, a nonempty set of vertices (or nodes) and E, a set of
edges. Each edge has either one or two vertices associated with it, called its endpoints. An
edge is said to connect its endpoints.

We often let n = |V| and m = |E|.

A graph is visualized by using points to represent vertices and line segments (possibly curved)
to represent edges. The endpoints of a line representing an edge are the points representing
the endpoints of the edge. Each vertex is labelled using different letters or numbers and each
edge is represented by set of endpoints or a string of endpoints.
Example 1

Vertex-set = V = {a, b, c, d, e}
Edge-set = E = {ab, ad, bc, bd, be, de}
or {{a, b}, {a, d}, {b, c}, {b, d}, {b, e}, {d, e}}
Note : ab = ba

Figure 1
A graph with at most one edge joining a given pair of vertices is called a simple graph. Two
vertices may have several edges joining them; such edges are called multiple edges, and a
graph having multiple edges is called a multigraph. A loop – an edge joining a vertex to itself,
may occur in a graph. A graph that includes loop(s) and possibly multiple edges is called a
pseudograph.
Example 2

Vertex-set = V = {a, b, c, d, e}
Edge-set = E = {ab, ad, ad, ad, bc, bd, be, be, de}

Figure 2 : A multigraph
 Vertex-set = V = {a, b, c, d, e}
Edge-set = E = {ab, ad, ad, ad, dd, bc, cc, bd, be,
be, de}

Figure 3 : A pseudograph

Definition 2
A directed graph (or digraph) G = (V, E) consists of V, a nonempty set of vertices (or nodes)
and E, a set of directed edges (or arcs). Each directed edge is associated with an ordered
pair of vertices. The directed edge associated with the ordered pair (u, v) is said to start at u
and end at v.

When a digraph has no loops and has no multiple directed edges, it is called a simple digraph.
A digraph that may have a multiple directed edges from a vertex to a second (possibly the
same) vertex is called a directed multigraph.
Example 3
x y

Vertex-set = V = {w, x, y, z}
Edge-set = E = {(x, y), (x, w), (x, z), (y, z), (w, x),
(w, z), (z, y)}

w z
Figure 4 : A simple digraph

x y

Vertex-set = V = {w, x, y, z}
Edge-set = E = {(x, y), (x, y), (x, w), (x, w), (x, z), (y,
z), (w, x), (w, z), (z, y), (z, z)}

z
w

Figure 5 : A directed multigraph

Adjacency and Degrees
Undirected graph

Definition 3
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 e of G. Such an edge e is called incident with the vertices u
and v and e is said to connect u and v.

Definition 4
Two edges e and f in an undirected graph G are adjacent in G if they have the same
endpoint. For example, e = uv and f = vw.

Definition 5
The set of all neighbours of a vertex v of G = (V, E), denoted by N(v), is called the
neighbourhood of v. If A is a subset of V, we denote N(A) the set of all vertices in G that are
adjacent to at least one vertex in A. So, N(A) = vA N(v ) .

Definition 6
The degree of a vertex in an undirected graph is the number of edges incident with it,
except that a loop at vertex contributes twice to the degree of that vertex. The degree of the
vertex v is denoted by deg(v) or d(v).

(G) is the minimum degree of a vertex of G and ( G) is the maximum degree of a vertex of G.
d(G) = n1 vV d (v ) is the average degree of G. Note that (G) ≤ d(G) ≤ ( G).

A vertex of degree 0 is an isolated vertex and a vertex of degree 1 is an end-vertex or a

pendant. The degree sequence of a graph consists of the degrees written in increasing order,
with repeats where necessary.
Example 4

a b deg(a) = 2, deg(b) = 3, deg(c) = 0,

•c deg(d) = 1, deg(e) = 3, deg(f) = 3.
c is an isolated vertex and d is a pendant.
f d Degree sequence : (0, 1, 2, 3, 3, 3)

e
 N(b) = {a, f, e}
If A = {e, f), N(A) = {a, b, d}

Theorem 1 (The handshaking lemma)

Let G = (V, E) be an undirected graph with m edges. Then the sum of all the vertex-degrees
is an even number and 2m =  deg(v ) .
v V

Proof : Since each edge is incident to two vertices, then each edge contributes exactly 2 to the
sum of the vertex-degrees. Hence, the sum is twice the number of edges and its even.
Example 5
Refer to the graph in example 4.
The number of edges, m = 6
The sum of all the vertex-degrees = 0+1+2+3+3+3 =12.

Thus, the sum of all the vertex-degrees is even and 2m = 12 =  deg(v )

v V

Theorem 2
In any undirected graph the number of vertices of odd degree is even.

Proof : Let V1 and V2 be the set of vertices of even degrees and the set of vertices of odd
degrees, respectively, in an undirected graph G = (V, E) with m edges. Then

2m =  deg(v ) =  deg(v ) +  deg(v ) .

v V v V1 v V2

Because the deg(v) is even for v  V1, the first term in the right-hand side of the above equality
is even. Furthermore, the sum of the two terms on the right-hand side is even, which is 2m.
Hence, the second term in the sum is also even. Because all the terms in this sum is odd, there
must be an even number of such terms. Thus, there are an even number of vertices of odd
degree.

Directed graph

Definition 7
When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and
v is said to be adjacent from u. The vertex u is called the initial vertex of (u, v), and v is
called the terminal or end vertex of (u, v).
 Definition 8

In a graph with directed edges the in-degree of a vertex v, denoted by deg−(v), is the
number of edges with v as the terminal vertex. The out-degree of a vertex v, denoted by
deg+(v), is the number of edges with v as the initial vertex.

Theorem 3
Let G = (V, E) be a graph with directed edges. Then

 deg (v ) =  deg (v ) = |E|.

v V
−

v V
+

Example 6

x y
deg−(w) = 1, deg−(x) = 1, deg−(y) = 2, deg−(z) = 3
deg+(w) = 2, deg+(x) = 3, deg+(y) = 1, deg+(z) = 1
The number of edges, m = 7

 deg (v ) = 1+1+2+3=7 and

v V
−

w z  deg (v ) = 2+3+1+1=7
v V
+

Thus,  deg (v ) =  deg (v ) = |E| =7

v V
−

v V
+

Representing graphs
Adjacency list
A graph can be represented using an adjacency list, which specify the vertices that are
adjacent to each vertex of the graph.
Example 7
Adjacency list : (simple graph)

a b Vertex Adjacent
•c vertices

a b, f

f b a, e, f
d
c -
d e
e
e b, d, f
f a, b, e

Adjacency matrix
Suppose that G = (V, E) is a simple graph where |V| = n. Suppose that the vertices of G are
listed arbitrarily as v1, v2, …, vn. The adjacency matrix A (or AG) of G, with respect to this listing
of the vertices, is the n  n 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, ie A = [aij], where

1 if {vi, vj} is an edge of G,

aij =
0 otherwise

Example 8
Use an adjacency matrix to represent the graph below.

a b
Adjacency matrix with respect to the ordering
a, b, c, d, e :

0 1 1 0 0
c d 1 0 1 0 1

A = 1 1 0 0 1
 
0 0 0 0 1
e 0 1 1 1 0 
Example 9

0 1 1 0
1 0 0 1
Draw a graph with the adjacency matrix  with respect to the ordering a, b, c, d.
1 0 0 1
 
0 1 1 0
a c

b
d

Facts :
1. An adjacency matrix is based on the ordering chosen for the vertices. Hence, there may
be as many as n! different adjacency matrices for a graph with n vertices.
2. The adjacency matrix of a simple graph is symmetric.
3. The adjacency matrix of a simple graph has the main diagonal entries 0.

An adjacency matrix can also be used to represent a pseudograph. A loop at the vertex vi is
represented by a 1 at the (i, i)th position of the adjacency matrix. When multiple edges
connecting the same pair of vertices vi and vj, then the (i, j)th position of the matrix is the
number of edges that are associated to {vi, vj}. All undirected graphs, including multigraphs and
pseudographs, have symmetric adjacency matrices.

Example 10
Use an adjacency matrix to represent the pseudograph below.
Adjacency matrix with respect to the
ordering a, b, c, d, e :

0 1 0 3 0
1 0 1 1 2 

A = 0 1 1 0 0
 
3 1 0 1 1
0 2 0 1 0 
An adjacency matrix for a directed graph has a 1 in its (i, j)th position if there is an edge from vi
to vj, where v1, v2, …, vn is an arbitrary listing of the vertices of the directed graph, ie A = [aij],
where

1 if (vi, vj) is an edge of G,

aij =
0 otherwise

The adjacency matrix for a directed graph does not have to be symmetric.
Example 11
Use an adjacency matrix to represent the directed graph below.

x y
Adjacency matrix with respect to the
ordering w, x, y, z :

1 0 0 1
1 0 1 1
A= 
0 0 0 1
 
w z 0 0 1 0
Incidence matrix
Let G = (V, E) be an undirected graph. Suppose that v1, v2, …, vn are the vertices and e1,
e2, …, em are the edges of G. Then the incidence matrix with respect to the ordering of V and
E is the n  m matrix M = [mij], where

1 when edge ej is incident with vi,

mij =
0 otherwise

Example 12
Represent the graph below with an incidence matrix.
The incidence matrix :
a e1 b

e2 e3 e1 e2 e3 e4 e5 e6
e5 a 1 1 0 0 0 0
c d b  1 0 1 0 1 0 
e6 M=
e4 c 0 1 1 1 0 0
 
d 0 0 0 0 0 1
e e 0 0 0 1 1 1 

Example 13
Represent the pseudograph below with an incidence matrix.

e1
e10
e3 e4
e2 e5
e8 e9

e11
e7
e6
 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11
a 1 1 1 1 0 0 0 0 0 0 0
b  1 0 0 0 1 0 0 1 1 1 0 
The incidence matrix : M =
c 0 0 0 0 0 0 0 0 0 1 1
 
d 0 1 1 1 1 1 1 0 0 0 0
e 0 0 0 0 0 0 1 1 1 0 0 

Isomorphism

Definition 9
The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there exists 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.

Example 14
Show that the graphs G = (V, E) and H = (W, F) given below are isomorphic.
u1 u2 v1 v2

u3 u4 v3 v4
G H
The function f with f(u1) = v1, f(u2) = v4, f(u3) = v3, and f(u4) = v2 is one-to-one correspondence
between V and W. This correspondence preserves adjacency :

Adjacent vertices in G Adjacent vertices in H

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

u1 and u3 f(u1) = v1 and f(u3) = v3

u2 and u4 f(u2) = v4 and f(u4) = v2

u3 and u4 f(u3) = v3 and f(u4) = v2

In any two isomorphic graphs, the number of vertices, the number of edges, and the degree
sequence are preserved. If any of these quantities differ in two simple graphs, these graphs
cannot be isomorphic. However, when these quantities are the same, it does not necessarily
mean the two graphs are isomorphic.
Example 15
Show that the graphs G and H given below are not isomorphic.
b b

a a
c c

e d e d
G H

Number of vertices Number of edges Degree sequence

G 5 6 (2, 2, 2, 3, 3)

H 5 6 (1, 2, 2, 3, 4)

Both G and H have 5 vertices and 6 edges. However, the degree sequences of G and H are
different. Hence, G and H are not isomorphic.
Example 15
Determine whether the graphs G and H shown below are isomorphic.

a b s t
e f w x

h z
g y
d c v u
G H

Number of vertices Number of edges Degree sequence

G 8 10 (2, 2, 2, 2, 3, 3, 3, 3)

H 8 10 (2, 2, 2, 2, 3, 3, 3, 3)

Both G and H have 8 vertices and 10 edges, and both graphs have the same degree sequence.
We now try to find an isomorphism f.
Since deg(a) = 2 in G, f(a) can either be t, u, x or y, because these are the vertices of degree 2
in H. In G, N(a) = {b, d} where deg(b) = 3 and deg(d) = 3. But in H,
N(t) = {s, u} where deg(s) = 3 and deg(u) = 2,
N(u) = {v, t} where deg(v) = 3 and deg(t) = 2,
 N(x) = {w, y} where deg(w) = 3 and deg(y) = 2,
N(y) = {z, x} where deg(z) = 3 and deg(x) = 2.
Thus, f(a) cannot be t, u, x nor y and hence G and H are not isomorphic.

Example 16
Determine whether the graphs G and H shown below are isomorphic.

u1 u2 v1 v3
v2
u5 v6
u6 y
u4 u3 v5 v4
G H

Number of vertices Number of edges Degree sequence

G 6 7 (2, 2, 2, 2, 3, 3)
H 6 7 (2, 2, 2, 2, 3, 3)

The graphs G and H are isomorphic with isomorphism f :

f(u1) = v6, f(u2) = v3, f(u3) = v4, f(u4) = v5, f(u5) = v1, f(u6) = v2.

The preservation of edges by f can be examined using the adjacency matrix of G and the
adjacency matrix of H with the rows and columns labelled by the images of the corresponding
vertices in G.
u1 u2 u3 u4 u5 u6 v6 v3 v4 v5 v1 v2
u1 0 1 0 1 0 0 v 6 0 1 0 1 0 0
u2  1 0 1 0 0 1 v 3  1 0 1 0 0 1
A G = u3  0 1 0 1 0 0 AH = v 4  0 1 0 1 0 0
   
u4  1 0 1 0 1 0 v5 1 0 1 0 1 0
u5  0 0 0 1 0 1 v 1 0 0 0 1 0 1
   
u6 0 1 0 0 1 0  v 2 0 1 0 0 1 0 
Types of graphs
Null graphs
A graph whose edge-set is empty is a null graph. Each vertex of a null graph is isolated. The
null graph on n vertices is denoted by Nn.

• •
• •
• •
• • • •
N4 N6

Complete graphs
A complete graph on n vertices, denoted by Kn, is a simple graph that contains exactly one
edge between each pair of distinct vertices. Kn has 21 n(n – 1) edges.

•
K1 K2 K3 K4 K5

Cycle graphs
A cycle graph, Cn, n ≥ 3 consists of n vertices is a connected graph in which each vertex has
degree 2.

C3 C4 C5 C6

Path graphs
A path graph on n vertices, Pn, is obtained from Cn by removing an edge.

P2 P3 P6
Wheels
A wheel on n vertices, Wn, is obtained from Cn-1 by joining each vertex to a new vertex.

W5 W6 W9

Regular graphs
A graph in which each vertex has the same degree is a regular graph. If each vertex has
degree r, the graph is regular of degree r or r-regular.
Nn is 0-regular; Cn is 2-regular; Kn is (n – 1)-regular

Cubic graphs
A regular graph of degree 3 is called a cubic graph. An example of a cubic graph is the
Petersen graph.

Petersen graph
Platonic graphs
Platonic graphs are regular graphs formed from the vertices and edges of the five regular
(Platonic) solids – the tetrahedron, octahedron, cube, icosahedron and dodecahedron.

n-cubes
An n-cube is an n-dimensional hypercube, denoted by Qn, is a graph that has vertices
representing 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.
We can construct the (n + 1)-cube Qn+1 from the n-cube Qn by making two copies of Qn,
prefacing the labels on the vertices with a 0 in one copy of Qn and with a 1 in the other copy of
Qn, and adding edges connecting two vertices that have labels differing only in the first bit.

0 1
Q1

To construct Q2,
00 01
0 1 00 01

0 1 10 11 10 11
Make two Preface first copy Add edges between
copies of Q1 with 0; second vertices with
copy with1 different preface
To construct Q3,

00 01 000 001 000 001

00 01 100 101 100 101

10 11 010 011 010 011

10 11 110 111 110 111
Make two copies of Preface first copy Add edges
Q2 with 0; second between vertices
copy with1 with different
preface

Bipartite graphs
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1
and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2, so that no
edge in G connects either two vertices in V1 or two vertices in V2.

a r
V1 = {a, b}
b s V2 = {r, s, t}

Alternatively, a bipartite graph is one whose vertices can be coloured black and white in such a
way that each edge joins a black vertex and white vertex.
Example 17
C6 is bipartite :
Complete bipartite graphs
A complete bipartite graph is a bipartite graph in which each vertex in V1 is joined to each
vertex in V2 by just one edge. We denote the complete bipartite graph with r black vertices and s
white vertices by Kr,s.

Operations and properties

Subgraphs

Definition 10

A subgraph of a graph G = (V, E) is a graph H = (W, F) where W  V and F  E. A

subgraph H of G is a proper subgraph of G if H  G.

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 of set F contains an edge in E if and only if both endpoints of
this edge are in W.

Example 17
a a
Subgraph of K5 :
e b e b

d c c
a
Subgraph induced by {a, b, c, e} :
e b

c
Union

If G1 = (V1, E1) and G2 = (V2, E2), then their union, G1  G2 is the graph with vertex set V1  V2
and edge set E1  E2.

Example 18
a x a x
a)

 y = y

b z b z
G1 G2 G1G2

b c a b c b c
b) a a

 =

d e d f d e f

Removing or Adding edges

Given a graph G = (V, E) and an edge e  E, G – e is a subgraph of G obtained by deleting the

edge e. Hence, G – e = (V, E – {e}).
Similarly, if F is a subset of E, G – F is the graph obtained by deleting edges in F and G–
F = (V, E – F).
We can also add an edge e to a graph to produce a new larger graph when this edge connects
two vertices already in G. The new graph is denoted by G + e and hence, G + e = (V, E
 {e}).

Edge contractions
We denote G\ e the graph obtained by taking an edge e and contracting it, which removes the
edge e with endpoints u and v and merges u and v into a new single vertex w, and for each
edge with u or v as an endpoint replaces the edge with w as endpoint in place of u or v and with
the same second endpoint. Hence, G\ e = G’ = (V’, E’) is not a subgraph of G, where V’ = V –
{u, v}  {w} and E’ contains the edges in E which do not have either u or v as endpoints and an
edge connecting w to every neighbour of either u or v in V.
Removing vertices
When we remove a vertex v and all edges incident to it from G = (V, E), we produce a
subgraph, denoted by G – v, and G – v = (V – {v}, E’), where E’ is the set of edges of G not
incident to v.
Similarly, if W is a subset of V, G – W is the subgraph (V – W, E’), where E’ is the set of edges
of G not incident to a vertex in W.

u v u v u w
e

G G–e G−v G\ e

Complement
If G is a simple graph with vertex set V, its complement G is the simple graph with vertex set V
in which two vertices are adjacent if and only if they are not adjacent in G.
y y

u x u
x

v w v
w
G G

Traversability : Walk, path, trail, cycle

A walk in a graph is a sequence of the form v1e1v2e2…vr for some r ≥ 1 where the vi is a vertex
and ei is an edge incident with vi and vi+1, for each 1≤ i ≤ r. If r = 1, the walk consists of a single
vertex and no edges.
Note : Edges and vertices may be repeated in a walk.
A walk with no repeated edge is a trail.
A path is a walk in which no vertex appears more than once, ie a sequence of distinct vertices
v1, v2, …, vk such that vivi+1 is an edge for 1≤ i ≤ k – 1.
The length of a path P is the number of edges in P.
A path of length greater then zero that begins and ends at the same vertex is called a cycle or a
circuit.
Theorem : A graph is bipartite if and only if all its cycles are even.
A chord of a path/ cycle is an edge between two vertices of the path/ cycle that is not on the
path/ cycle. Pn is the chordless path on n vertices, n ≥ 1 and Cn is the chordless cycle on n
vertices, n ≥ 3.

v → w → x → y → z → z → y → w is a walk of
x length 7 from v to w

v → w → x → y → z → z → x is a trail
v w z
v → w → x → y → z is a path

v → w → x → y → z → x → v is a closed trail
y
v → w → x → y → v is a cycle
Note that a loop is a cycle of length 1, and a pair of multiple edges is a cycle of length 2. A cycle
of length 3 is called a triangle.

Eulerian graphs

Definition 11
An Eulerian circuit in a graph G is a simple circuit containing every edge of G. An Eulerian
A path
graphin G
G isis Eulerian
a simpleifpath
there exists a closed
containing trail of G.
every edge

A graph G is Eulerian if it contains an Eulerian circuit. A non-Eulerian graph G is semi-Eulerian

if it contains an Eulerian path. An Eulerian graph is traversable.

Eulerian Semi-Eulerian Non-Eulerian

Non-Eulerian Eulerian Semi-Eulerian

Lemma 3
If G is a graph in which the degree of each vertex is at least 2, then G contains a cycle.

Theorem 4
A connected graph G is Eulerian if and only if the degree of each vertex of G is even.

Corollary 5
A connected graph G is semi-Eulerian if and only if it has exactly two vertices of odd
degree.

Theorem 6

A digraph G is Eulerian if and only if for each vertex v of G deg+(v) = deg−(v).

Hamiltonian graphs

Definition 12
A simple path in a graph G that passes through every vertex exactly once is called a
Hamiltonian path, and a simple circuit in a graph G that passes through every vertex exactly
once is called a Hamiltonian circuit.

A graph with a Hamiltonian circuit is a Hamiltonian graph. A non-Hamiltonian graph is semi-

Hamiltonian if there exists a Hamiltonian path in it.

Hamiltonian Semi-Hamiltonian Non-Hamiltonian

Dodecahedron is a Hamiltonian graph – a cycle is shown with

solid lines.

Theorem 7 (Ore)
If G is simple graph with n (≥ 3) vertices, and if deg(v) + deg(w) ≥ n for each pair of non-
adjacent vertices v and w, then G is Hamiltonian.

The tournament is a Hamiltonian digraph – two Hamiltonian cycles

are shown, one with solid lines and the other one with dotted lines.

A graph is connected if every pair of distinct vertices is joined by a path. Otherwise it is

disconnected.
A maximal connected graph of G is called a component of G. Thus, a disconnected graph has
at least two components.
The distance between two vertices u and v, dist(u, v) is the length of the shortest path joining
them.

max dist (u,v )

u,v V
The diameter of a connected graph G = (V, E), diam(G) is
The minimum length of a cycle in a graph G is the girth of G, g(G).
The circumference of G, c(G), is the length of any longest cycle.
A clique of a graph is a maximal complete subgraph

Weighted graphs
We can assign a non-negative number to each edge of a graph. Such a graph is called a
weighted graph, and the number assign to each edge e is the weight of e, denoted by w(e).
The weight may represent distance, time, or cost. The problem is to find the shortest path. A
weighted graph or network can be represented by a distance matrix. The matrix records the
weights on the edges. Where there is no edge, we write ‘-‘.

B
Weighted graph
23
17
19
A 15 E
16
18 D
20
C

Distance matrix

A B C D E

A - 17 18 - -
B 17 - 15 19 23
C 18 15 - 20 -
D - 19 20 - 16
E - 23 - 16 -
Chinese Postman Problems (Route inspection)
The Chinese Postman problem algorithm can be used to find the shortest route that traverses
every edge at least once and returns to the starting point.

• If all the vertices have even degree the network is traversable. The length of the shortest
route will be equal to the weight of the network.

Solve the Chinese Postman problem for the network below, starting and finishing at A.

A 11 B
All vertices have even degree, so the network is
10 7 traversable. A possible route is
E
ABECDEA
9 8
Length = 11 + 7 + 8 + 12 + 9 + 10 = 57
D 12 C

• If there are only two odd vertices, repeat the shortest path between them, and add it to
the network.

Find a minimal route, starting and finishing at S, that traverses each edge at least once. State
your route and its length.
P
6 Q
2
Vertices Q and T, both are of odd degree. 5
3
Thus, the shortest path Q to T need to be included. U S 7
Two extra edges, QS and ST of length 9 are added
2 4
to the network.
T 8 R
P
6 Q
2 5 A possible route is
3 5 SPQSQRTSTUS
U S 7
4 Weight of the network = 3+2+6+7+8+2+4+5 = 37
2 4
T 8 R Length of the route = 37 + 9 = 46.

• If there are more than two vertices with odd degree, we need to consider all possible
complete pairings and select the one that gives the smallest total and then add this
pairing to the network.
• Chinese Postman problem algorithm
 1. Identify vertices with odd degree.
2. Consider all possible complete pairings of these vertices.
3. Select the complete pairing that has the least sum.
4. Add a repeat of the edges indicated by this pairing to the network.
Solve the Chinese Postman problem for this network starting and finishing at A. State your route
and its length.

B 17 C
12
22
A 12
19 19
15 35
7
21 G E D
8 21
30
28
H 29
14
F

Vertices with odd degree : A, G, F and E

Possible pairings : A, G and F, E : AG + FE = 19 + 28 = 47
A, F and G, E : AHF + GE = 21 + 14 + 7 = 42
A, E and F, G : AGE + FHG = 19 + 7 + 14 + 8 = 48
The least sum is 42; add edges AH, HF and GE. A possible route is
ABCGBDCEFDEGEHFHGAHA
The weight of the network = 309
The length of the shortest route = 309 + 42 = 351

The network with the extra edges added

B 17 C
12
22
A 12
19 19
15 35
7
21 G E D
8 21
30
28
H 29
14
F