Graph Theory

Dr. Safaa O. Al-mamory

Department of Software 1
 Motivations (Königsberg Bridge)
 Graph theory begins with the Königsberg Bridge Problem;
this problem motivated the birth of the subject.
 In 1736, Königsberg was a city on the Pregel River in
Prussia and was renowned for its beautiful bridges.
(Königsberg is now Kaliningrad, Russia.)
 (Königsberg Bridge Problem). Is it possible, starting from
some place in Königsberg, to go for a walk that passes over
each bridge exactly once and returns to the starting place?

Department of Software 2
 Motivations (Airlines Services)
 To plan a trip involving these cities, one needs to
determine which direct flights to take. Costs and lengths
of these flights may also need to be considered.

Department of Software 3
 Motivations (Scheduling Conflicts)
 Six classes (Astronomy, Biology, Calculus, Discrete Math,
English Composition, and French) need to schedule study
group sessions. In the displayed table, an X denotes that the
two different classes corresponding to that row and column
have a student in common.

Department of Software 4
Introduction
 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.
 Note: The set of vertices V of a graph G may be
infinite. A graph with an infinite vertex set is called
an infinite graph, and in comparison, a graph with a
finite vertex set is called a finite graph. In this
chapter, we will usually consider only finite graphs.

Department of Software 5
 Introduction
 The graph in the figure contains three vertices, a, b,
and c: V = {a,b,c}. Its three edges are e1 = {a, a}, e2
= {a,b},and e3 = {b,c} : E={e1,e2,e3} = {{a,a},
{a,b}, {b,c}}.

Department of Software 6
Simple & Multigraph
 A graph in which each edge connects two different
vertices and where no two edges connect the same
pair of vertices is called a simple graph.
 Graphs that may have multiple edges connecting the
same vertices are called multigraphs.

Department of Software 7
 Degree of Vertex
 The degree of a 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
the vertex v is denoted by deg(v).
 The degrees of the vertices in the following graphs are as
below:
deg(a) = 2 ,
deg(b) = deg(c) = deg(f ) = 4 ,
deg(d ) = 1 ,
deg(e) = 3 ,
and deg(g) = 0.
Department of Software 8
 Vertex Degree (Cont.)
 Theorem 8.1: The sum of the degrees of the vertices of a
graph G is equal to twice the number of edges in G.
 Example:

-deg(a) +deg(b)+deg(c) +deg(d )+deg(f ) +deg(e)+deg(g) = 18

- Number of edges = 9
 A vertex of degree zero

is called an isolated vertex.

 A vertex is even or odd according as its degree is an even or an

odd number.

Department of Software 9
 Adjacency Matrix
The adjacency matrix of a graph with n vertices v1,
v2,…, vn is an n × n matrix A = (aij), where aij=number
of edges from vi to vj.

Department of Software 10
 Paths & Connectivity
 Informally, 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.
 A walk in a graph G = (V, E) is an alternating list of vertices
and edges
v0, e1, v1, e2, v2, e3, . . . , vn−1, en, vn
with n ≥ 0 that starts at vertex v0, ends at vertex vn,
 The length of a walk is the number of edges it contains
(counting multiple occurrences of the same edge), here n.

Department of Software 11
 Paths & Connectivity (Cont.)
 A circuit is a walk of positive length that starts and ends
at the same vertex.
 A trail is a walk with no repeated edges. In a graph with
multiple edges, distinct multiple edges may be included.
 A path is a walk with no repeated vertices.
 A cycle is a circuit in which the only vertex repetition is
vn = v0.

Department of Software 12
 Paths & Connectivity (Cont.)
 In the Direct Flights Graph, the walk
Los Angeles to New York to London to Rome to
NewYork to Chicago to Los Angeles
represents a circuit, since it starts and ends in Los
Angeles. Since New York is repeated, this walk is not a
cycle. However, since no edge is repeated, it is a trail.

Department of Software 13
 Paths & Connectivity (Cont.)
 A graph G is connected if, for any two vertices, there is
a path between them. Otherwise, G is disconnected.

 Figure a is connected; Figure b is disconnected.

 The vertex B in is called an isolated vertex since B does
not belong to any edge or, in other words, deg(B) = 0.
Department of Software 14
 Labeled & Weighted Graph
 A graph G is called a weighted graph if each edge e of G is
assigned a nonnegative number w(e) called the weight or
length of v.

 The length of a path is the sum of the weights of the edges

in the path.
 The length of a shortest path between P and Q in the figure
is 14; one such path is (P,A1,A2,A5,A3,A6,Q)
Department of Software 15
 Distance and Diameter
 The distance between vertices u and v in G, written d(u, v),
is the length of the shortest path between u and v.
 The diameter of G, written diam(G), is the maximum
distance between any two points in G.
 For example, in the Figure (a), d(A,F) = 2 and diam(G)=3,
whereas in Figure (b), d(A,F) = 3 and diam(G) = 4.

Department of Software 16
Cutpoints and Bridges
 Let G be a connected graph. A vertex v in G is called
a cutpoint if G−v is disconnected.
 An edge e of G is called a bridge if G−e is
disconnected.
 In Figure (a), the vertex D is a cutpoint and there are
no bridges. In Figure (b), the edge={D,F} is a bridge.
(Its endpoints D and F are necessarily cutpoints.)

Department of Software 17
 Traversable Graph
 A multigraph is said to be traversable if:
- it can be drawn without any breaks in the curve and
- it can be drawn without repeating any edges,
that is, if there is a path which includes all vertices and uses
each edge exactly once. Such a path must be a trail (since no
edge is used twice) and will be called a traversable trail.
 A traversable multigraph must be finite and connected.

 Any finite connected graph with two odd vertices is

traversable. A traversable trail may begin at either odd
vertex and will end at the other odd vertex.
Department of Software 18
 Eulerian Graph
 A path in a connected graph is an Eulerian path if it contains every
edge exactly once.
 A circuit in a connected graph is an Eulerian circuit if it contains
every edge of the graph.
 A connected graph with an Eulerian circuit is an Eulerian graph.

Eulerian Circuit Eulerian path, no Eulerian path,

no Eulerian circuit no Eulerian circuit
A connected graph G is Eulerian if and only if
every vertex of G has even degree.
Department of Software 19
Eulerian Graph
 a

Department of Software 20
Hamiltonian Graph
 Hamiltonian circuit is a closed path that visits every
vertex in G exactly once. (Such a closed path must be
a cycle.)
 If G does admit a Hamiltonian circuit, then G is
called a Hamiltonian graph.

Repeated Edges? Repeated Vertices?

Eulerian Circuit No Yes
Hamiltonian Circuit Yes No

Department of Software 21
Hamiltonian Graph
 Find a mail route through the pictured neighborhood
that hits every mailbox exactly once and returns to its
start?

Department of Software 22
Hamiltonian Graph Examples

Department of Software 23
 Traveling Salesman Problem
 Note the Figure. The vertices represent cities and the
weights represent the distances between them. A salesman
assigned to city a would like to visit every other city exactly
once and return to the home city so that the total distance
traveled is a minimum. In other words, beginning at a, he
would like to find a Hamiltonian cycle, so the sum of the
weights along the cycle is a minimum.

Department of Software 24
 Complete Graph
 A graph G is said to be complete if every vertex in G is
connected to every other vertex in G. Thus a complete graph
G must be connected. The complete graph with n vertices is
denoted by Kn. Figure 8-13 shows the graphs K1 through K6.

Department of Software 25
 Regular Graph
 A graph G is regular of degree k or k-regular if every vertex
has degree k. In other words, a graph is regular if every
vertex has the same degree.

Department of Software 26
 Bipartite Graph
 A graph G is said to be bipartite if its vertices V can be
partitioned into two subsets M and N such that each edge of
G connects a vertex of M to a vertex of N.
 By a complete bipartite graph, we mean that each vertex of
M is connected to each vertex of N; this graph is denoted by
Km,n where m is the number of vertices in M and n is the
number of vertices in N.

Department of Software 27
 PlanarGraph
 A graph or multigraph which can be drawn in the plane so
that its edges do not cross is said to be planar.

Department of Software 28
 Maps & Regions
 A particular planar representation of a finite planar
multigraph is called a map. We say that the map is
connected if the underlying multigraph is connected.
 A given map divides the plane into various regions.
 By the degree of a region r, written deg(r), we mean the
length of the cycle or closed walk which borders r.

 The sum of the degrees of the

regions of a map is equal to twice
the number of edges.
Department of Software 29
 Graph Coloring
 A vertex coloring, or simply a coloring of G is an
assignment of colors to the vertices of G such that adjacent
vertices have different colors.
 We say that G is n-colorable if there exists a coloring of G
which
 The minimum number of colors needed to paint G is called
the chromatic number of G and is denoted by χ(G). uses n
colors.

Department of Software 30
Dual Maps & The Four Color Theorem
 Any planar graph is 4-colorable

Department of Software 31
 Be ready for the
exam on the next
lecture

Department of Software 32
 References
1. Seymour Lipschutz, and Marc Lipson, “Schaum’s
Outlines: Discrete Mathematics,” 3rd edition, McGraw-
Hill, 2007.
2. Rosen, Discrete Mathematics and Its Applications, 6th
edition, 2007.
3. Kevin Ferland, Discrete Mathematics, An Introduction
To Proofs And Combinatorics, Richard Stratton, 2009.
4. Thomas Koshy, Discrete Mathematics with Applications,
Elsevier Press, 2004.

Department of Software 33
 Thank You for
Listening.

Department of Software 34