G RAPH T HEORY
Introduction
Chapter 1
Ralph El Khoury
Faculté des Sciences - Branche II
Université Libanaise
1 / 58
Outline
1 Introduction
2 Applications
3 Subgraphs
4 Degrees, in-degrees, and out-degrees
5 Degree vectors of simple graphs
6 Problems
2 / 58
Introduction
Introduction
Graph theory abstracts and simplifies real-world problems
. So we can understand relationships between things.
A graph is a mathematical representation of a relationship
. ”dots” (i.e. vertices) are used to represent people, computers,
cities, and so on.
. ”Line segments” (i.e. edges) are used to demonstrate which
vertices are related and how there are related.
Definition
A graph G = (V , E) is defined by a set of vertices V , and a set of
edges E consisting of unordered pairs of vertices from V .
3 / 58
Introduction
(a) Multi-graph with n=7 et m=8
(b) Simple Graph with n=6 et m=5 4 / 58
Introduction
Definitions
Let V = {v1 , v2 , . . . , vn } (or V (G)) and E = {e1 , e2 , . . . , em } (or
E(G))
. The order n of a graph is the number of its vertices
. Its size m is the number of its edges.
If u and v are two vertices of a graph
. Each edge e is of the form {u, v } or uv .
. Vertices u and v are said to be incident on e, and e is incident to
u and v .
. We say that e joins u and v .
. u and v are said to be adjacent if uv ∈ E(G).
5 / 58
Introduction
Definitions
Two or more edges that join the same pair of distinct vertices are
called parallel.
An edge uv in which u = v is a loop.
A multi-graph is a graph that permits multiple edges between
given pairs of vertices.
A simple graph is a graph with no parallel edges and no loops.
A complete graph, denoted by Kn , is a graph where all pairs of
vertices are adjacent.
. The number of edges in Kn is:m = n2 = n(n−1)
2
. This number is an upper bound for the number of edges of any
graph G: m ≤ n(n−1)
2
6 / 58
Introduction
Complete Graph: number of edges
Complete Graph
7 / 58
Introduction
(a) Complete Graphs
(b) A Path
(c) Cyclic Graphs
8 / 58
Introduction
K1 with one vertex and no edges is known as the trivial graph.
A bipartite graph is a simple graph in which the set of vertices
can be partitioned into two sets X and Y such that every edge is
between a vertex in X and a vertex in Y .
The complete bipartite graph Km,n is the graph (X , Y , E) with m
vertices in X and n vertices in Y in which there is an edge
between every vertex in X and every vertex in Y .
A cyclic graph Cn = (V , E) or cycle (where n > 2) is exactly
what you think it is
. If V = {1, 2, . . . , n}, then E = {{1, 2}, {2, 3}, . . . , {n − 1, n}, {n, 1}}
. A triangle is a cyclic graph.
The path on n vertices is denoted Pn . Pn is a graph obtained from
Cn by deleting a single edge.
9 / 58
Introduction
(a) Bipartite Graph
X = {x1 , x2 } and Y = {y1 , y2 , y3 } (b) Complete Bipartite Graph
10 / 58
Introduction
A directed graph or digraph
It consists of a finite set V of vertices and a set A of ordered pairs
of distinct vertices called arcs.
If the ordered pair {u, v } or uv is an arc a, we say that the arc a is
directed from u to v .
In this context, arc a is adjacent from vertex u and is adjacent to
vertex v .
11 / 58
Introduction
(a) Directed Graph or Digraph
(b) Weigthed Graph
12 / 58
Applications
Applications
These are some applications of the graph theory:
1 Map and transportation
2 Managing a natural park
3 Computer Science: networking, web, etc.
4 Social network analysis
5 Business application: warehouses/retail stores
6 Chemistry application
7 Ice cream truck routing
8 Traveling salesman problem
9 Scheduling exams
10 Project scheduling
11 Assignment
13 / 58
Applications
Map and transportation
Consider a graph G with
. V (G) = {v1 , v2 , v3 , v4 , v5 } representing five cities
. E(G) = {v1 v2 , v2 v3 , v2 v5 , v5 v4 , v4 v1 } representing direct airline
flights
The numbers on each edge represent distances traveled by each
flight.
Find the shortest way to get from v4 to v3 .
Interconnection of cities
14 / 58
Applications
Map and transportation
Google Map: find the shortest path between two points. Vertices are
roads intersection and edges are the roads.
Google Map
15 / 58
Applications
Managing a natural park
This park has many stations where we can find many (historical or
natural) sites to watch, or simply stations to take some rest.
The problems to solve in this park are
. Find the shortest path from the entrance of the park until the end
where we can find a beautiful site.
. Install telephone lines to connect all the stations together such as
the total length of the lines is minimized. This is the problem of the
minimum spanning tree.
. Each road in this site can be traversed a limited number of times in
a day. How many times at most can we traverse with a bus a road,
and which roads? This is the problem of flow.
16 / 58
Applications
Natural Park
17 / 58
Applications
Computer Science
Graphs are non-linear data structures that stores information
about any graph application
For example, data about maps are stored in matrices or adjacency
lists. Then graph algorithms are implemented and applied to solve
a problem concerning this graph.
In networking : a communication network is represented by a
graph
In the Web: links between pages in a given website or between
different websites. For example, Page Ranking.
In a software, modules are related to each others. Vertices are
modules and edges are the relations.
In an operating system: resource allocation, e.g. allocating
registers to variables, allocating resources to processes.
18 / 58
Applications
Computer Science: networking
A graph G represents the network, where
. Vertices are computers
. Edges are lines between them.
We can add a weight on each edge which represents : bandwidth,
delay, and so on.
A weighted graph is a graph that associates to each edge a
value.
Questions :
. Find the shortest path in terms of number of intermediate lines or
high bandwidth, etc...?
19 / 58
Applications
(a) Communication Network
(b) Flow Network
20 / 58
Applications
Computer Science: Web
PageRank algorithm considers the number of links into a web page
and the quality of the linking sites to determine the importance of the
page.
Page Ranks using Web sites links
21 / 58
Applications
Social Network Analysis
In a social network like facebook, each person is a vertex and the
relationship between two persons is the edge.
We can study the relationship between persons using a social
network graph.
Social network
22 / 58
Applications
Business Application: Warehouses/Retail Stores
Businesses use graphs to model which of several warehouses
service retail stores.
. Suppose V = {w1 , w2 , w3 , r1 , r2 , r3 , r4 , r5 } represents 3 warehouses
and 5 retail stores.
. Suppose E = {w1 r1 , w1 r2 , w2 r2 , w2 r3 , w2 r4 , w3 r3 , w3 r5 } represents
the relation of each warehouse to each retail store.
Note that we can split V into 2 disjoint subsets and get a bipartite
graph.
A bipartite graph is a simple graph in which the set of vertices
can be partitioned into two sets X and Y such that every edge is
between a vertex in X and a vertex in Y .
The transport problem: we need to satisfy the need of the stores
with the lowest transportation cost.
23 / 58
Applications
(b) Transport Network
(a) Warehouses/Retail Stores
24 / 58
Applications
Chemistry Application
Modeling and studying simple hydrocarbons (e.g. C4 H10 ) with a
special type of graph called a tree.
A tree is a connected graph without any cycle.
Trees are also studied
. in computer science as a type of data structure, used for example
to store and search for data.
. in social science to represent hierarchies. E.g., families genealogy.
25 / 58
Applications
Ice cream truck routing
The graph G (in the following figure) represents streets in a town
as edges, and street intersections as vertices.
Question
. If an ice cream truck begins at vertex 5, can the ice cream
salesperson travel along each street exactly once and return back
to vertex 5?
This problem is related to eulerian graphs.
26 / 58
Applications
Traveling salesman problem
Suppose a computer representative has to travel by plane to five
cities and return to her home city.
How can she accomplish this assignment if she is to visit each city
only once.
This problem is related to hamiltonian graphs.
In this problem, we are generally concerned with total distance
traveled and how to minimize this travel.
27 / 58
Applications
(b) Airlines between cities.
Hamiltonian Graph
(a) Streets in a town.
Eulerian Graph
Eulerian and Hamiltonian tours are used to help a company to
distribute their merchandises to shops in a town. There exists many
other applications.
28 / 58
Applications
Scheduling exams
A professor needs to schedule six final exams so that no students
has a conflict.
. Let G be the representative graph with V = {a, b, c, d, e, f } the six
courses offering finals.
. Join two vertices with an edge if the two courses they represent
have at least one student in common.
. Different colors can represent different time slots.
Scheduling exams is equivalent to assigning each vertex (i.e.
course) a color (i.e. a time slot) while assuring that courses
connected by an edge have different colors (time slots)
Question: how to color the vertices to get an optimal schedule?
This problem is related to graph coloring.
29 / 58
Applications
Common students from different courses - Graph coloring
30 / 58
Applications
Project Scheduling
A graph or a graph network enable us to see the relationships
between the activities.
Each activity is represented by a vertex.
The arcs then are used just to show the precedence relationships
between the activities
The weight in the graph represents duration.
Questions
What is the duration of the project.
What are the critical activities that could not be late.
Which activities can be late and for how long.
31 / 58
Applications
Project network: activities for constructing a new plant
32 / 58
Applications
Assignment
Consider a graph whose vertices represent people,
. where an edge connects people who are friends
These people are planning to go a long bus ride, and seats are
assigned in pairs
The travel director would like to pair friends so that they will have
an enjoyable trip.
Question: how you will assign seats?
Another example could be ”Job assignment”.
This problem is related to matchings in graph.
33 / 58
Applications
(b) Job assignment
(a) Friendship
34 / 58
Subgraphs
Subgraphs
The graph H = (W , F ) is a subgraph of the graph G = (V , E)
. If W is a subset of V and F is a subset of E.
Particular examples:
. If a subgraph H of the graph G is a cyclic graph, H is called a cycle
in G.
. A complete subgraph of G is a clique in G.
We have two interesting particular types of subgraphs
. Spanning subgraph
. Induced subgraph
35 / 58
Subgraphs
Subgraphs
36 / 58
Subgraphs
Find a cycle and a clique
37 / 58
Subgraphs
Spanning subgraph
Any subgraph H = (V , F ) of G = (V , E) where V (H) = V (G) is a
spanning subgraph.
We may simply form a spanning subgraph by deleting edges from
G.
If F is a set of edges in G = (V , E)
. The graph G − F is a spanning subgraph
. If F consists of one edge f , we write G − f the spanning subgraph.
38 / 58
Subgraphs
Induced subgraph
If W ⊆ V (G) then the subgraph induced by W (or the induced
subgraph), denoted < W > is
. the subgraph consisting of W and all edges of the form uv of G,
where u ∈ W and v ∈ W .
Among all subgraphs of G that use W as the vertex set, < W >
has the maximum number of edges possible.
Observe that the subgraph G − W is the induced subgraph
<V −W >
Remark
If W ⊆ V (G) and there are k edges that join the vertices of W within a
graph G, then there are 2k subgraphs of G that use W as the vertex
set
39 / 58
Subgraphs
Number of spanning subgraphs N
40 / 58
Degrees, in-degrees, and out-degrees
Degrees
In a graph with no loops,
. the degree of a vertex v is, denoted deg(v ) (or degG (v )), is the
number of edges incident to v .
If there are p loops at a vertex v that has also q edges (not loops)
incident to it
. Thus, deg(v ) = 2p + q
An isolated vertex is a vertex with degree 0.
An end-vertex is a vertex with degree 1.
The maximum degree among the vertices of a graph is denoted
∆(G).
The minimum degree is denoted δ(G).
A graph is k-regular if the degree of each vertex is k.
It is called regular if δ(G) = ∆(G).
41 / 58
Degrees, in-degrees, and out-degrees
(a) deg(b)=2, deg(c)=3, deg(d)=1=δ(G), deg(a)=4=∆(G)
(b) k -regular graphs: k = 2 for K3 ,C4 and C5 ; k = 3 for K4 42 / 58
Degrees, in-degrees, and out-degrees
Theorem 1: The handshaking lemma
The sum of thePdegrees of any graph G = (V , E) is twice the number
of edges in it: u∈V degG (u) = 2m. So, the sum of the degrees of the
vertices is a nonnegative even integer
43 / 58
Degrees, in-degrees, and out-degrees
A vertex in a graph is an odd vertex if its degree is odd. Otherwise it is
an even vertex.
Theorem 2
Every graph has an even number of odd vertices.
44 / 58
Degrees, in-degrees, and out-degrees
In-degrees, and out-degree
Digraphs case
The number of arcs adjacent to a vertex is the in-degree of that
vertex.
The number of arcs adjacent from a vertex is the out-degree of
that vertex.
When the out-degrees (or in-degrees) of all the vertices are
added, each arc is considered once in the counting process.
45 / 58
Degrees, in-degrees, and out-degrees
Theorem 3
In a digraph, the sum of the out-degrees of all the vertices is equal to the
number of arcs, which is equal to the sum of all the in-degrees of all the
vertices.
46 / 58
Degree vectors of simple graphs
Degree vectors of simple graphs
The degree vector d(G) of a simple graph is the sequence of
degrees of its vertices arranged in a nonincreasing order.
d(G)=[3 2 2 1], degree vector
47 / 58
Degree vectors of simple graphs
Necessary conditions
di ≥ 0 ∀i
di ≤ n − 1 ∀i
Pn
i=1 di = 2m is even.
Remark
A vector having the necessary conditions true may not be a degree
vector. Example, v = [3 1 0 0].
48 / 58
Degree vectors of simple graphs
Graphical vector
A vector v is called a graphical vector if there exists a simple graph
such that v is the degree vector of that graph.
The following theorem gives a necessary and sufficient condition for a
vector to be a graphical vector:
Theorem 4: Hakimi-Havel theorem
Let [d1 d2 ... dn ] be a nonincreasing vector of n (where n is at least
2) nonegative integers such that no component di exceeds (n − 1).
Let v 0 be the vector obtained from v by deleting d1 and subtracting
1 from each of the next d1 components of v .
Let v1 be the nonincreasing vector obtained from v 0 by
rearranging its components if necessary.
Then v is a graphical vector if and only if v1 is a graphical vector.
Example
Verify if v = [5 4 3 3 3 3 3 2] is a graphical vector or not. 49 / 58
Degree vectors of simple graphs
Algorithm to test whether a given vector is graphical
The input is a nonincreasing vector v with integer components
Step 0. (Initialization) The current vector is v .
Step 1. If the current vector with n components has a component that exceeds
(n − 1), go to step 5. Otherwise, go to step 2.
Step 2. If the current vector has a negative component, go to step 5.
Otherwise go to step 3.
Step 3. If the current vector is the zero vector, go to step 6. Otherwise, go to
step 4.
Step 4. (Iteration) Rearrange the components of the current vector so that it
becomes nonincreasing with d1 as the first component. Delete d1 from
the rearranged vector, and subtract 1 from each of the next d1
components of the rearranged vector. The vector thus constructed is
updated current vector. Go to step 1.
Step 5. The input vector is not graphical. Go to step 7.
Step 6. The input vector is graphical. Go to step 7.
Step 7. Stop.
50 / 58
Degree vectors of simple graphs
Example
Verify if v = [5 4 4 3 3 3 2] is a graphical vector or not.
Iteration 1 v = [5 4 4 3 3 3 2] and v1 = [3 3 2 2 2 2]
Iteration 2 v = [3 3 2 2 2 2] and v1 = [2 2 2 1 1]
Iteration 3 v = [2 2 2 1 1] and v1 = [1 1 1 1]
Iteration 4 v = [1 1 1 1] and v1 = [1 1 0]
Iteration 5 v = [1 1 0] and v1 = [0 0]
At the end of the fifth iteration, we get the zero vector. So the given
vector is a graphical vector.
51 / 58
Problems
Problems
Problem 1
Determine the number of edges in a graph with 6 vertices, 2 of degree
4 and 4 of degree 2. Draw two such graphs.
Problem 2
How many vertices are needed to construct a graph with 6 edges in
which each vertex is of degree 2.
Problem 3
Is it possible to draw a simple graph with 4 vertices and 7 edges ?
Justify.
52 / 58
Problems
Problems
Problem 4
Draw the graph K2,3 . What is the number of edges m of the Kx,y graph
function of x and y?
Problem 5
Show that a finite nonincreasing vector in which no two components
are equal cannot be a graphical vector.
Problem 6
Implement Hakimi-Havel algorithm using the C++ language. Execute
your program and verify that the previous problem proposition is true.
53 / 58
Problems
Solutions
Problem 1
n = 6, di = 4 for 1 ≤ i ≤ 2; di = 2 for 3 ≤ i ≤ 6;
m: number of edges
From the handshaking Lemma: 2x4 + 4x2 = 16 = 2m ⇒ m = 8
Simple Graphs G1 and G2
54 / 58
Problems
Multigraphs G3 , G4 and G5
55 / 58
Problems
Problem 2
n =?, m = 6, di = 2 for 1 ≤ i ≤ n
From the Handshaking theorem: 2xn = 2m = 2x6 ⇒ n = 6
Problem 3
n = 4, m = 7 ⇒ G? simple graphe.
For any simple graphe, we should have m ≤ n(n−1)
2 , i.e. m should be
less or equal than the number of edges in a complete graph Kn , but
n(n−1)
2 = 6 < m = 7 ⇒ we cannot draw a simple graph.
56 / 58
Problems
Problem 4
Let X = {x1 , x2 } and Y = {y1 , y2 , y3 }. m = |X |x|Y |
Complete bipartite Graph K2,3
57 / 58
Problems
Problem 5
Let v be this vector with n components. v = d1 d2 ... dn such as
di 6= dj ∀i, j i 6= j. Given that no 2 components are equal, the only
way to write this vector is:
v = n − 1 n − 2 ... 1 0 .
By applying
the Hakimi-Havel theorem
to v we obtain:
v = n − 3 n − 4 ... 0 −1
which contains a negative component, so the vector is not graphical.
58 / 58
