MATH 1130 1 Discrete Structures

Reference: K.H. Rosen, Discrete Mathematics and Its Applications, 5

th
Edition, McGraw-Hill, 2003. Daricks Chan
Chapter IV Graph Theory

Terminology of Graph

Graphs
A graph G is a discrete structure consisting of nodes (called vertices) and lines joining the nodes
(called edges). Two vertices are adjacent to each other if they are joint by an edge. The edge
joining the two vertices is said to be an edge incident with them. We use ( ) G V and ( ) G E to
denote the set of vertices and edges of G respectively.

Example




u and v are adjacent vertices; e is an edge incident with u and v. e can also be denoted by uv or vu.

Loops and Multiple Edges
An edge joining only one vertex is called a loop. If there are more than one edge joining u and v of G,
then all edges joining u and v form a multiple edge of G.






Simple Graph
A simple graph is a graph containing no loops and multiple edges.

Degrees of Vertices
The degree of a vertex 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 the vertex v is denoted by ( ) v deg or
( ) v d .

Example

( ) 5 = u d , ( ) 3 = v d and ( ) 2 = w d

u v
e
u v
A loop
A multiple edge
u v
w
MATH 1130 2 Discrete Structures

Reference: K.H. Rosen, Discrete Mathematics and Its Applications, 5
th
Edition, McGraw-Hill, 2003. Daricks Chan
Theorem [The handshaking theorem] Let G be a graph with e edges. Then
( )
( )

=
G V v
v d e 2

Theorem The number of vertices of odd degree in a graph G is even.

Complete Graphs
The complete graph on n vertices, denoted by
n
K , is the simple graph in which any pair of vertices
are adjacent.

Examples

I)
1
K II)
2
K



III)
3
K IV)
4
K



Bipartite Graphs
A simple graph G is called bipartite if its vertex set ( ) G V can be partitioned into two disjoint sets of
1
V and
2
V such that every edge in the graph connects a vertex in
1
V and a vertex in
2
V . In other
words, any two vertices in the same set
1
V (and
2
V ) are not adjacent.

Example





Complete Bipartite Graphs
A complete bipartite graph, denoted by
n m
K
,
, is the bipartite graph with m V =
1
and n V =
2
, and
( ) G E vu if and only if
1
V v and
2
V u .

Example



1
V
2
V
4 , 3
K
MATH 1130 3 Discrete Structures

Reference: K.H. Rosen, Discrete Mathematics and Its Applications, 5
th
Edition, McGraw-Hill, 2003. Daricks Chan
Subgraphs
A subgraph of a graph G is a graph H where ( ) ( ) G V H V and ( ) ( ) G E H E .

Example






Incidence Matrices
Let G be an graph. Suppose
n
v v v , , ,
2 1
K are the vertices and
m
e e e , , ,
2 1
K are the edges of G.
Then the incidence matrix with respect to this ordering of ( ) G V and ( ) G E is the m n matrix
] [
ij
m M = , where

=
otherwise. 0
, ith incident w is when 1
i j
ij
v e
m

Example







Adjacency Matrices
Let G be an graph. Suppose
n
v v v , , ,
2 1
K are the vertices of G. Then the adjacent matrix with
respect to this ordering of ( ) G V is the n n matrix ] [
ij
m M = , where

=
otherwise. 0
, adjacent are and when 1
j i
ij
v v
m

Example





is a subgraph of
1
v
2
v
3
v
4
v
5
v
The corresponding adjacency matrix is

0 1 1 0 0
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
0 1 1 1 0

1
v
2
v
3
v
4
v
5
v
1
e
2
e
6
e
5
e
3
e
4
e
7
e
The corresponding incidence matrix is

0 1 1 0 0 0 0 0
1 1 0 1 0 1 0 0
1 0 1 0 1 0 1 0
0 0 0 1 1 0 0 1
0 0 0 0 0 1 1 1

8
e
MATH 1130 4 Discrete Structures

Reference: K.H. Rosen, Discrete Mathematics and Its Applications, 5
th
Edition, McGraw-Hill, 2003. Daricks Chan
Paths and Cycles
In a graph G, a path of length n from u to v is a sequence of 1 + n vertices
1 2 1
, , , ,
+ n n
v v v v K where
u v =
1
and v v
n
=
+1
, and ( ) G E v v
i i

+1
for n i , , 2 , 1 K = . A path is called a circuit when v u = . A
path or a circuit is simple if it does not contain the same edge more than once. A cycle is a circuit in
which all vertices are distinct.

Connected Graphs
A graph is connected if there is a path between every pair of distinct vertices of the graph. An edge
uv in a connected graph G is called a bridge if uv G , the graph obtained by deleting uv from G, is
not connected.

Example

A connected graph





Euler Circuit and Euler 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.

Theorem A connected graph has an Euler circuit if and only if each of its vertices has even
degree.

Algorithm [Fleurys Algorithm] to Construct an Euler Circuit
procedure Euler Circuit
circuit v u, := , any ( ) G E uv
uv G G = :
while ( ) G E
circuit = : circuit with w, ( ) G E vw and v is the last vertex in
circuit (vw should not be a bridge in G unless there is
no other vertices in ( ) G E adjacent to v.)
vw G G = :
end {circuit is an Euler circuit}

A Bridge
MATH 1130 5 Discrete Structures

Reference: K.H. Rosen, Discrete Mathematics and Its Applications, 5
th
Edition, McGraw-Hill, 2003. Daricks Chan
Proof Suppose that we follow the algorithm above started from u to extend the circuit in G and have
just reached a vertex v. We also assume the next move must be a bridge. It is noted that all
vertices in G except u and v must be of even degree. We shall show in the following that
there is only one remaining edge incident with v. Suppose contrary that there are more than
one remaining edge incident with v. Then, in v G (the graph obtained by deleting v and
all its incident edges from G), there are more than one connected subgraph and least one of
them does not contain u. In the connected subgraph not containing u, the only vertex of odd
degree is the vertex adjacent to v in G. This is a contradiction to the fact that there should be
even number of odd vertices in a graph. Hence, any moves over a bridge will separate the
graph into one connected subgraph and an isolated vertex. After finitely many steps, all
edges will be included in the circuit.











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

Proof Let G be a connected graph. If G contains an Euler path u v v v v P
n
, , , , ,
2 1
K = , then
v u v v v v
n
, , , , , ,
2 1
K is an Euler circuit in uv G+ . From the theorem above, all vertices in
uv G+ are of even degree; hence there are exactly two odd vertices u and v of G.
Conversely, if there are exactly two odd vertices u and v of G, then all vertices in uv G+ (a
graph obtained by adding uv to G) must be of even degree. It follows that uv G+ has an
Euler circuit v u v v v v C
n
, , , , , ,
2 1
K = ; hence, u v v v v
n
, , , , ,
2 1
K is an Euler path in G.

Example


Bridges
v
u
The only vertex of odd degree in this subgraph
MATH 1130 6 Discrete Structures

Reference: K.H. Rosen, Discrete Mathematics and Its Applications, 5
th
Edition, McGraw-Hill, 2003. Daricks Chan
Hamilton Paths and Hamilton Cycles
A path
n
v v v , , ,
2 1
K containing all vertices in G and
j i
v v for all n j i 1 is called Hamilton
path. A cycle
1 2 1
, , , , v v v v
n
K in G is a Hamilton cycle if
n
v v v , , ,
2 1
K is a Hamilton path.

Theroem [Ores Theorem] If G is a simple graph with n vertices with 3 n such that
( ) ( ) n v d u d + for every pair of nonadjacent vertices u and v in G, then G has a
Hamilton cycle.

Proof http://www.ecp6.jussieu.fr/pageperso/bondy/research/papers/shortproofs.ps

Theorem [Diracs Theorem] If G is a simple graph with n vertices 3 n such that the degree of
every vertex in G is at least 2 n , then G has a Hamilton cycle.

Proof For any ( ) G V v u , , ( ) ( ) n
n n
v d u d = + +
2 2
. From Ores Theorem, G has a Hamilton
cycle.

Shortest Path Problems

Weighted Graphs
A graph has a number (weight) assigned to each edge is called a weighted graph.

Example

A weighted graph




Shortest Path
A path in a weighted graph such that the sum of the weights of the edges in this path is a minimum
over all paths between specified vertices is called a shortest path.

1
2
6
1
7
2
3
4
MATH 1130 7 Discrete Structures

Reference: K.H. Rosen, Discrete Mathematics and Its Applications, 5
th
Edition, McGraw-Hill, 2003. Daricks Chan
Algorithm [Dijkstras Algorithm] for Producing Shortest Paths from a Fixed Vertex
procedure Dijkstra (G: a weighted connected simple graph, with all weights positive)
{G has vertices
n
v v v v , , , ,
2 1 0
K and weights ( )
j i
v v w . ( ) =
j i
v v w if ( ) G E v v
j i
}
for 1 := i to n
( ) = :
i
v L
( ) 0 :
0
= v L
= : S
while ( ) G V S
= : u a vertex not in S with ( ) u L minimal
{ } u S S = :
for all vertices v not in S
if ( ) ( ) ( ) v L uv w u L < + then ( ) ( ) ( ) uv w u L v L + = :
end {the lengths of shortest paths from
0
v }

Example

Consider a to be the fixed vertex.





Tabular Method
S ( ) a L ( ) b L ( ) c L ( ) d L ( ) e L ( ) f L ( ) g L Predecessor
0
a 2
2
6
6
5
5





a
a,b 3
3

5
6
6



b
a,b,c 6
5
5
5
10
10
8
8 a
a,b,c,d
5

10
11
8 c
a,b,c,d,e 9
9

8 c
a,b,c,d,e,g 11
9

e
a,b,c,d,e,g,f

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