Math 162: Introduction to graph theory
Ümit Işlak
Boğaziçi Üniversitesi, Matematik Bölümü
Ümit Işlak Math 162: Introduction to graph theory
A graph G is expressed with a set V containing the vertices,
and set E containing the edges that connect certain vertices
in V . Such a graph is denoted by G = (V, E).
If the edges have initial and terminal points, then the graph is
said to directed. Otherwise we say that the graph is
undirected.
In an undirected graph, an edge connecting the vertices v1 , v2
is represented by {v1 , v2 } or (v1 , v2 ).
Ümit Işlak Math 162: Introduction to graph theory
We see an example of an undirected graph with 5 vertices and 5
edges in following figure:
Ümit Işlak Math 162: Introduction to graph theory
Below you see a portion of Erdös graph.
Paul Erdös (1913-1996) is one of the most prolific mathematicians
of all times. He wrote around 1500 papers with more than 500
collaborators, and this made him a symbol for collaboration in
mathematics.
Ümit Işlak Math 162: Introduction to graph theory
Because of his tendency to collaboration, an Erdös number is
assigned to each mathematician - you may learn your number
easily on web. Authors with a joint paper with Erdös have Erdös
number 1, those who did not write a paper with Erdös but wrote
with a collaborator of Erdös have Erdös number 2, and so on. If
you haven’t written a paper or if you are isolated, then your Erdös
number at the moment is ∞.
Ümit Işlak Math 162: Introduction to graph theory
Another example is the web graph in which the vertices are the
web sites and the edges are links.
Ümit Işlak Math 162: Introduction to graph theory
https:
//www.internetlivestats.com/total-number-of-websites/
Ümit Işlak Math 162: Introduction to graph theory
Definitions
If there are mulltiple edges between vertices or if there are
loops, then the graph is said to be a multigraph. (For
example, if we look at a communication graph via e-mail
among people, then that would be a multigraph.
A graph with no multiple edges and no loops is said to be a
simple graph. (Movie stars graph is simple.)
If v and w are at two ends of an edge, then they are said to
be adjacent. We show this by v ↔ w. (Jeremy Irons and
Meryl Streep are adjacent in movie stars graph.)
If the vertex v is at one end of an edge e, then we say that v
is incident to e. We denote this v ∈ e.
Ümit Işlak Math 162: Introduction to graph theory
Ümit Işlak Math 162: Introduction to graph theory
Definitions
Degree of a vertex is the number of edges incident to it
(For example, in our movie stars graph, degree of Jeremy
Irons = 1, degree of Meryl Streep = 3, etc.). The degree of
vertex v is denoted by dv or deg(v).
A vertex sequence v1 , . . . , vk ∈ V , such that vi ↔ vi+1 , and
vi 6= vj , i 6= j, is said to be a path. (Using abbreviations, in
movie stars, JI, MS, DH, RR is a path.)
We call paths with the same initial and terminal vertex a
closed path. (In our movie stars graph, MS, RR,DH, MS
forms a closed path.)
If we may find a path between any two vertices, then the
graph is said to be connected. (Our movie stars graph is
connected. If we include my name in that graph, it is no
longer connected.) A graph that is not connected is called
disconnected.
Ümit Işlak Math 162: Introduction to graph theory
Definitions
Degree of a vertex is the number of edges incident to it
(For example, in our movie stars graph, degree of Jeremy
Irons = 1, degree of Meryl Streep = 3, etc.). The degree of
vertex v is denoted by dv or deg(v).
A vertex sequence v1 , . . . , vk ∈ V , such that vi ↔ vi+1 , and
vi 6= vj , i 6= j, is said to be a path. (Using abbreviations, in
movie stars, JI, MS, DH, RR is a path.)
We call paths with the same initial and terminal vertex a
closed path. (In our movie stars graph, MS, RR,DH, MS
forms a closed path.)
If we may find a path between any two vertices, then the
graph is said to be connected. (Our movie stars graph is
connected. If we include my name in that graph, it is no
longer connected.) A graph that is not connected is called
disconnected.
Ümit Işlak Math 162: Introduction to graph theory
Definitions
Degree of a vertex is the number of edges incident to it
(For example, in our movie stars graph, degree of Jeremy
Irons = 1, degree of Meryl Streep = 3, etc.). The degree of
vertex v is denoted by dv or deg(v).
A vertex sequence v1 , . . . , vk ∈ V , such that vi ↔ vi+1 , and
vi 6= vj , i 6= j, is said to be a path. (Using abbreviations, in
movie stars, JI, MS, DH, RR is a path.)
We call paths with the same initial and terminal vertex a
closed path. (In our movie stars graph, MS, RR,DH, MS
forms a closed path.)
If we may find a path between any two vertices, then the
graph is said to be connected. (Our movie stars graph is
connected. If we include my name in that graph, it is no
longer connected.) A graph that is not connected is called
disconnected.
Ümit Işlak Math 162: Introduction to graph theory
Handshake lemma
Theorem. In any graph, the number of vertices with odd degree is
even.
Proof. Let G = (V, E) be our graph where V is the vertex set and
E is the edge set. If dv denotes the degree of vertex v, then we
have X
dv = 2|E|.
v∈V
(Why?). This says
X X
2|E| = dv + dv .
|{z}
even v: dv even v: dv odd
| {z }
even
P
So, v: dv odd dv must be an even number since it is the difference
of two even numbers. This can occur if and only if the number of
vertices with odd degree is even.
Ümit Işlak Math 162: Introduction to graph theory
Examples of real graphs
Acquaintance graphs
Web graph
Erdös graph
Bacon graph
···
Ümit Işlak Math 162: Introduction to graph theory
Acquaintance graphs
In acquaintance graphs, vertices represent the people, and the
edges are the friendships between them.
Examples: Facebook, Linkedin, Twitter, etc.
Definition: Given two vertices u, v of G, the distance
between the vertices u, v, denoted d(u, v), is the length of the
shortest path between these two vertices.
Definition: In a connected graph, the maximum of d(u, v)
over all u, v is called the diamater of the graph.
Ümit Işlak Math 162: Introduction to graph theory
Acquaintance graphs
In acquaintance graphs, vertices represent the people, and the
edges are the friendships between them.
Examples: Facebook, Linkedin, Twitter, etc.
Definition: Given two vertices u, v of G, the distance
between the vertices u, v, denoted d(u, v), is the length of the
shortest path between these two vertices.
Definition: In a connected graph, the maximum of d(u, v)
over all u, v is called the diamater of the graph.
Ümit Işlak Math 162: Introduction to graph theory
Ümit Işlak Math 162: Introduction to graph theory
Milgram experiment
Stanley Milgram asserted that certain acquaintance graphs have
diameter 6: ”Six degrees of separation”
Milgram, Stanley. ”The small world problem.” Psychology today
2.1 (1967): 60-67.
Milgram, S., Travers, J., ”An Experimental Study of the Small
World Problem”, 1969.
300 people from Nebraska, Boston and Omaha are chosen
randomly.
These people are told to transfer a letter to specific person in
Boston.
The letters can be passed to only a first degree acquaintance.
% 20 of the letters reached.
These reached in 6 steps on the average.
Ümit Işlak Math 162: Introduction to graph theory
Ümit Işlak Math 162: Introduction to graph theory
Web graph
In web graph, the vertices are the web sites, the edges are the
links between them.
There are billions of web sites and trillions of web pages.
Trying to understand this via the adjacency matrix makes the
underlying difficulty clear.
Is the information only a few cliques away?
Bonato, A., ”A course on the web graph”, AMS, 2009.
Ümit Işlak Math 162: Introduction to graph theory
Web graph
In web graph, the vertices are the web sites, the edges are the
links between them.
There are billions of web sites and trillions of web pages.
Trying to understand this via the adjacency matrix makes the
underlying difficulty clear.
Is the information only a few cliques away?
Bonato, A., ”A course on the web graph”, AMS, 2009.
Ümit Işlak Math 162: Introduction to graph theory
Web graph
Web graph, like our other examples, is a dynamic graph.
How does the growth of the graph occur?
”Rich gets richer”
”Preferential attachment model”.
Ümit Işlak Math 162: Introduction to graph theory
Degree sequence
Our definition for the degree sequence of a graph is as follows: Let
Nk be the number of vertices whose degree is k. Then the degree
sequence is defined to be the vector (N0 , N1 , . . . , Nn ).
Ümit Işlak Math 162: Introduction to graph theory
Degree sequence
Given the degree sequence (N0 , N1 , . . . , Nn ), dividing each entry
by the total number of vertices, we may form a probability vector
(p0 , p1 , . . . , pn ).
First random graph models proposed by researchers were not
successful in imitating the degree sequences of real life networks.
Later it was observed that the degree sequences in these networks
behave according to the power law (Pareto/Zipf/Yule-Simon,etc.).
This means
pk ∼ Ck −β , C > 0, β > 1.
Albert-Barabasi model:
https://arxiv.org/pdf/cond-mat/0106096.pdf
”Black swan”
Ümit Işlak Math 162: Introduction to graph theory
Blue: Power law
Green: Exponential
Black: Poisson
Red: Exponential/Power
Ümit Işlak Math 162: Introduction to graph theory
Note that there is another natural definition for the degree
sequence (What is it?). After finding it out check the following
paper: Choudum, Sheshayya A. ”A simple proof of the
Erdos-Gallai theorem on graph sequences.” Bulletin of the
Australian Mathematical Society 33.1 (1986): 67-70.
Ümit Işlak Math 162: Introduction to graph theory
Collaboration graphs
Bacon graph:
Kevin Bacon (Tremors, Mystic River, Apollo 13, etc.) once
claimed that he worked with everybody at Hollywood and some
other guys decide to test this.
Ümit Işlak Math 162: Introduction to graph theory
https://oracleofbacon.org/movielinks.php
Ümit Işlak Math 162: Introduction to graph theory
Bacon number / Number of people
Ümit Işlak Math 162: Introduction to graph theory
Consider a graph G = (V, E) with n vertices. The clustering
coefficient of v ∈ V is defined by
{(u, w) ∈ E : (u, v) ∈ E, (w, v) ∈ E}
Cv = deg(v)
.
2
This is a measure of ”Friends of mine are also friends”.
Clustering coefficient of the graph G = (V, E) is defined to be
1X
C(G) = Cv .
n
v∈V
Clustering coefficient of daily graphs turn out to be around 0.15 ±
0.05.
Ümit Işlak Math 162: Introduction to graph theory
Summary
Real networks
have the small worlds property.
are dynamic.
(Type II) degree sequences satisfy the power law.
have the rich gets richer property.
have clustering coefficient around 0.15.
Real networks are modelled probabilistically.
One such important example is the preferential attachment model.
Ümit Işlak Math 162: Introduction to graph theory
Summary
Real networks
have the small worlds property.
are dynamic.
(Type II) degree sequences satisfy the power law.
have the rich gets richer property.
have clustering coefficient around 0.15.
Real networks are modelled probabilistically.
One such important example is the preferential attachment model.
Ümit Işlak Math 162: Introduction to graph theory
Königsberg problem. In the eightenth century the inhabitants of
Königsberg in Eastern Prusia were puzzled over the now-famous
problem of whether they could go on a walking tour of their city
crossing each of the seven bridges once and only once. The city of
Königsberg looked like this - bridges are represented with a red:
Ümit Işlak Math 162: Introduction to graph theory
Representing each bridge by a line and collapsing each land mass
to a single point we are able to see that this is equivalent to
drawing the figure below in one continuous piece without covering
any stretch of line twice.
ANSWER: NO
Ümit Işlak Math 162: Introduction to graph theory
Reading suggestions
Watts ve Strogatz, Small Worlds
Stanley Milgram papers
Nassim Taleb, Black swan
Wilson, Intro to graph theory
Hofstadt, Random graphs and complex networks
Albert ve Barabasi, Linked
Ümit Işlak Math 162: Introduction to graph theory
Last question of the day
Consider the following 20 cities of Turkey that are marked with
red.
We are willing to connect all these cities to each other with duble
yols. The rule is as follows: These 20 cities will be connected to
each other but there will not be any unnecessary ways. Of course
here all 20
2 = 190 possible ways have distinct costs. How can we
have the minimal cost duble yol network under our rule?
Ümit Işlak Math 162: Introduction to graph theory
Elveda
Next time: Euler and Hamiltonian tours
Selamlar, iyi çalışmalar,
Ümit
Ümit Işlak Math 162: Introduction to graph theory
