Graph Theory

Varying Applications (examples)

 Computer networks
 Distinguish between two chemical compounds
with the same molecular formula but different
structures
 Solve shortest path problems between cities
 Scheduling exams and assign channels to
television stations
Topics Covered
 Definitions
 Types
 Terminology
 Representation
 Sub-graphs
 Connectivity
 Hamilton and Euler definitions
 Shortest Path
 Planar Graphs
 Graph Coloring
Definitions - Graph

A generalization of the simple concept of a set

of dots, links, edges or arcs.
Simple Finite Graph G=(V,E) consists of a finite
nonempty set V and a subset of 2-elements subset E
of V, that is E  V2, Where V2={ A V | |A|=2}.
Definitions – Edge Type
Directed: Ordered pair of vertices. Represented as (u, v)
directed from vertex u to v.

u v

Undirected: Unordered pair of vertices. Represented as {u, v}.

Disregards any sense of direction and treats both end vertices
interchangeably.

u v
Definitions – Edge Type
 Loop: A loop is an edge whose endpoints are equal
i.e., an edge joining a vertex to it self is called a loop.
Represented as {u, u} = {u}

 Multiple Edges: Two or more edges joining the

same pair of vertices.
Definitions – Graph Type
Simple (Undirected) Graph: consists of V, a nonempty set of
vertices, and E, a set of unordered pairs of distinct elements of
V called edges (undirected)
Representation Example: G(V, E), V = {u, v, w}, E = {{u, v}, {v,
w}, {u, w}}

u v

w
Definitions – Graph Type
Multigraph: G(V,E), consists of set of vertices V, set of
Edges E and a function f from E to {{u, v}| u, v V, u ≠ v}.
The edges e1 and e2 are called multiple or parallel edges if f
(e1) = f (e2).
Representation Example: V = {u, v, w}, E = {e1, e2, e3}

u
e1 e2
w

e3
v
Definitions – Graph Type
Pseudograph: G(V,E), consists of set of vertices V, set of Edges E
and a function F from E to {{u, v}| u, v Î V}. Loops allowed in
such a graph.
Representation Example: V = {u, v, w}, E = {e1, e2, e3, e4}

u
e1 w e4
e2

v e3
Definitions – Graph Type
Directed Graph: G(V, E), set of vertices V, and set of Edges E,
that are ordered pair of elements of V (directed edges)
Representation Example: G(V, E), V = {u, v, w}, E = {(u, v), (v,
w), (w, u)}

u v

w
Definitions – Graph Type
Directed Multigraph: G(V,E), consists of set of vertices V, set
of Edges E and a function f from E to {{u, v}| u, v V}. The
edges e1 and e2 are multiple edges if f(e1) = f(e2)
Representation Example: V = {u, v, w}, E = {e1, e2, e3, e4}

u
u e4
e1 e2

u e3
Definitions – Graph Type

Type Edges Multiple Edges Loops Allowed ?

Allowed ?
Simple Graph undirected No No

Multigraph undirected Yes No

Pseudograph undirected Yes Yes

Directed Graph directed No Yes

Directed directed Yes Yes

Multigraph
Terminology – Undirected graphs
 u and v are adjacent if {u, v} is an edge, e is called incident with u and v. u
and v are called endpoints of {u, v}

 Degree of Vertex (deg (v)): the number of edges incident on a vertex. A

loop contributes twice to the degree (why?).

 Pendant Vertex: deg (v) =1

 Isolated Vertex: deg (v) = 0

Representation Example: For V = {u, v, w} , E = { {u, w}, {u, w}, (u, v) },

deg (u) = 2, deg (v) = 1, deg (w) = 1, deg (k) = 0, w and v are pendant , k is
isolated

u v
k

w
Terminology – Directed graphs
 For the edge (u, v), u is adjacent to v OR v is adjacent from u, u – Initial
vertex, v – Terminal vertex

 In-degree (deg- (u)): number of edges for which u is terminal vertex

 Out-degree (deg+ (u)): number of edges for which u is initial vertex

Note: A loop contributes 1 to both in-degree and out-degree (why?)

Representation Example: For V = {u, v, w} , E = { (u, w), ( v, w), (u, v) }, deg-

(u) = 0, deg+ (u) = 2, deg- (v) = 1,
deg+ (v) = 1, and deg- (w) = 2, deg+ (u) = 0

u v

w
Theorems: Undirected Graphs
Theorem 1
The Handshaking theorem:
2e  v
vV

(why?) Every edge connects 2 vertices

 Theorems: Undirected Graphs
Theorem 2:
An undirected graph has even number of vertices with odd degree

Pr oof V 1 is the set of even degree vertices and V2 refers to odd degree vertices
2e   deg(v)   deg(u)   deg(v)
vV u  V1 v  V2

 deg (v) is even for v  V1,

 The first term in the right hand side of the last inequality is even.
 The sum of the last two terms on the right hand side of
the last inequality is even since sum is 2e.
Hence second term is also even
 second term  deg(v)  even
v  V2
Theorems: directed Graphs
 Theorem 3:  deg + (u) =  deg - (u) = |E|
Simple graphs – special cases
 Complete graph: Kn, is the simple graph that contains exactly
one edge between each pair of distinct vertices.

Representation Example: K1, K2, K3, K4

K1 K2 K3
K4
Simple graphs – special cases
 Cycle: Cn, n ≥ 3 consists of n vertices v1, v2, v3 … vn and edges
{v1, v2}, {v2, v3}, {v3, v4} … {vn-1, vn}, {vn, v1}
Representation Example: C3, C4

C3 C4
Simple graphs – special cases
 Wheels: Wn, obtained by adding additional vertex to Cn and
connecting all vertices to this new vertex by new edges.
Representation Example: W3, W4

W3 W4
Simple graphs – special cases
 N-cubes: Qn, vertices represented by 2n bit strings of length n.
Two vertices are adjacent if and only if the bit strings that they
represent differ by exactly one bit positions
Representation Example: Q1, Q2

10 11

0 1

00 01

Q1 Q2
Bipartite graphs
 In a simple graph G, if 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 V2 (so that no edge in G connects
either two vertices in V1 or two vertices in V2)
Application example: Representing Relations
Representation example: V1 = {v1, v2, v3} and V2 = {v4, v5, v6},

v4
v1

v5
v2

v6
v3

V1 V2
Complete Bipartite graphs
 Km,n is the graph that has its vertex set portioned into two
subsets of m and n vertices, respectively There is an edge
between two vertices if and only if one vertex is in the first
subset and the other vertex is in the second subset.
Representation example: K2,3, K3,3

K2,3 K3,3
Subgraphs
 A subgraph of a graph G = (V, E) is a graph H =(V’, E’) where V’ is a
subset of V and E’ is a subset of E
Application example: solving sub-problems within a graph
Representation example: V = {u, v, w}, E = ({u, v}, {v, w}, {w, u}}, H1
, H2

u u u

v w v w v

G H1 H2
Subgraphs
 G = G1 U G2 wherein E = E1 U E2 and V = V1 U V2, G, G1 and G2 are
simple graphs of G

Representation example: V1 = {u, w}, E1 = {{u, w}}, V2 = {w, v},

E1 = {{w, v}}, V = {u, v ,w}, E = {{{u, w}, {{w, v}}

u
u

w v
w w v

G1 G2 G
 Representation
 Incidence (Matrix): Most useful when information about
edges is more desirable than information about vertices.

 Adjacency (Matrix/List): Most useful when information

about the vertices is more desirable than information about the
edges. These two representations are also most popular since
information about the vertices is often more desirable than
edges in most applications
Representation- Incidence Matrix
 G = (V, E) be an unditected graph. Suppose that v1, v2, v3, …, vn
are the vertices and e1, e2, …, em are the edges of G. Then the
incidence matrix with respect to this ordering of V and E is the nx
m matrix M = [m ij], where

1 when edge ej is incident w ith vi

m ij  
0 otherwise
Can also be used to represent :
Multiple edges: by using columns with identical entries, since
these edges are incident with the same pair of vertices
Loops: by using a column with exactly one entry equal to 1,
corresponding to the vertex that is incident with the loop
Representation- Incidence Matrix
 Representation Example: G = (V, E)

e1 e2 e3
u
v 1 0 1
e1 e2
u 1 1 0

v w w 0 1 1
e3
Representation- Adjacency Matrix
 There is an N x N matrix, where |V| = N , the Adjacenct Matrix
(NxN) A = [aij]

For undirected graph

1 if {vi, vj} is an edge of G
a ij  
0 otherwise
 For directed graph
1 if (vi, vj) is an edge of G
a ij  
0 otherwise

 This makes it easier to find subgraphs, and to reverse graphs if needed.

Representation- Adjacency Matrix
 Adjacency is chosen on the ordering of vertices. Hence, there
as are as many as n! such matrices.
 The adjacency matrix of simple graphs are symmetric (aij = aji)
(why?)
 When there are relatively few edges in the graph the adjacency
matrix is a sparse matrix
 Directed Multigraphs can be represented by using aij = number
of edges from vi to vj
Representation- Adjacency Matrix
 Example: Undirected Graph G (V, E)

v u w
u
v 0 1 1

u 1 0 1
v w
w 1 1 0
Representation- Adjacency Matrix
 Example: directed Graph G (V, E)

v u w
u
v 0 1 0

u 0 0 1
v w
w 1 0 0
Representation- Adjacency List
Each node (vertex) has a list of which nodes (vertex) it is adjacent

Example: undirectd graph G (V, E)

u
node Adjacency List

u v,w

v w, u
v w
w u,v
 Graph - Isomorphism
 G1 = (V1, E2) and G2 = (V2, E2) are isomorphic if:
 There is 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.
 Function f is called isomorphism

Application Example:
In chemistry, to find if two compounds have the same
structure
Graph - Isomorphism
Representation example: G1 = (V1, E1) , G2 = (V2, E2)
f(u1) = v1, f(u2) = v4, f(u3) = v3, f(u4) = v2,

u1 u2 v1 v2

u3 u4 v4
v3
Connectivity
 Basic Idea: In a Graph Reachability among vertices
by traversing the edges
Application Example:
- In a city to city road-network, if one city can be
reached from another city.
- Problems if determining whether a message can be
sent between two
computer using intermediate links
- Efficiently planning routes for data delivery in the
Internet
Connectivity – Path
A Path is a sequence of edges that begins at a vertex
of a graph and travels along edges of the graph,
always connecting pairs of adjacent vertices.

Representation example: G = (V, E), Path P

represented, from u to v is {{u, 1}, {1, 4}, {4, 5}, {5,
v}}

2
1 v
3
u

4 5
 Connectivity – Path
Definition for Directed Graphs
A Path of length k (> 0) from u to v in G is a sequence of k+1
vertices x1,x2,…xk+1 such that xixi+1 is an edge for i=1,2,…,k-1.

For Simple Graphs, sequence is x0, x1, …, xn

In directed multigraphs when it is not necessary to distinguish

between their edges, we can use sequence of vertices to
represent the path

Circuit/Cycle: u = v, length of path > 0

Simple Path: does not contain a vertex more than once

Connectivity – Connectedness
Undirected Graph
An undirected graph is connected if there exists is a
simple path between every pair of vertices

Representation Example: G (V, E) is connected since

for V = {v1, v2, v3, v4, v5}, there exists a path
between {vi, vj}, 1 ≤ i, j≤ 5
v4
v1 v3

v2 v5
Connectivity – Connectedness
Undirected Graph

 Articulation Point (Cut vertex): removal of a vertex

produces a subgraph with more connected components than in
the original graph. The removal of a cut vertex from a
connected graph produces a graph that is not connected
 Cut Edge: An edge whose removal produces a subgraph with
more connected components than in the original graph.
Representation example: G (V, E), v3 is the articulation point or
edge {v2, v3}, the number of connected components is 2 (> 1)

v3 v5
v1

v2
v4
Connectivity – Connectedness
Directed Graph
 A directed graph is strongly connected if there is a path from
a to b and from b to a whenever a and b are vertices in the
graph
 A directed graph is weakly connected if there is a
(undirected) path between every two vertices in the underlying
undirected path

A strongly connected Graph can be weakly connected but the

vice-versa is not true (why?)
Connectivity – Connectedness
Directed Graph
Representation example: G1 (Strong component), G2 (Weak
Component), G3 is undirected graph representation of G2 or G1

G1 G2 G3
Connectivity – Connectedness
 Directed Graph
Strongly connected Components: subgraphs of a
Graph G that are strongly connected
Representation example: G1 is the strongly connected
component in G

G G1
Isomorphism - revisited
A isomorphic invariant for simple graphs is the
existence of a simple circuit of length k , k is an
integer > 2 (why ?)
Representation example: G1 and G2 are isomorphic since we
have the invariants, similarity in degree of nodes, number of
edges, length of circuits

G1 G2
 Counting Paths
 Theorem: Let G be a graph with adjacency matrix A with respect to the
ordering v1, v2, …, Vn (with directed on undirected edges, with multiple
edges and loops allowed). The number of different paths of length r from
Vi to Vj, where r is a positive integer, equals the (i, j)th entry of
(adjacency matrix) Ar.

Proof: By Mathematical Induction.

Base Case: For the case N = 1, aij =1 implies that there is a path of length 1. This
is true since this corresponds to an edge between two vertices.

We assume that theorem is true for N = r and prove the same for N = r +1.
Assume that the (i, j)th entry of Ar is the number of different paths of length r from
vi to vj. By induction hypothesis, bik is the number of paths of length r from vi to vk.
Counting Paths
Case r +1: In Ar+1 = Ar. A,
The (i, j)th entry in Ar+1 , bi1a1j + bi2 a2j + …+ bin anj
where bik is the (i, j)th entry of Ar.

By induction hypothesis, bik is the number of paths of length r from vi

to vk.

The (i, j)th entry in Ar+1 corresponds to the length between i and j
and the length is r+1. This path is made up of length r from vi to vk
and of length from vk to vj. By product rule for counting, the number of
such paths is bik* akj The result is bi1a1j + bi2 a2j + …+ bin anj ,the
desired result.
 Counting Paths
a ------- b
| |
| |
c -------d

A=0110 A4 = 8 0 0 8
1001 0880
1001 0880
0110 8008

Number of paths of length 4 from a to d is (1,4) th entry of A4 = 8.

 The Seven Bridges of Königsberg, Germany
 The residents of Königsberg, Germany, wondered if it
was possible to take a walking tour of the town that
crossed each of the seven bridges over the Presel river
exactly once. Is it possible to start at some node and
take a walk that uses each edge exactly once, and
ends at the starting node?
 The Seven Bridges of Königsberg, Germany

You can redraw the original picture as long as for every edge between
nodes i and j in the original you put an edge between nodes i and j in
the redrawn version (and you put no other edges in the redrawn
version).

Original:
2 3

4
Redrawn: 2

4 1
3
 The Seven Bridges of Königsberg, Germany

Euler:

 Has no tour that uses each edge exactly once.

 (Even if we allow the walk to start and finish in different places.)
 Can you see why?
Euler - definitions
 An Eulerian path (Eulerian trail, Euler walk) in a graph is a
path that uses each edge precisely once. If such a path exists,
the graph is called traversable.

 An Eulerian cycle (Eulerian circuit, Euler tour) in a graph

is a cycle that uses each edge precisely once. If such a cycle
exists, the graph is called Eulerian (also unicursal).

 Representation example: G1 has Euler path a, c, d, e, b, d, a, b

a b

c d e
 The problem in our language:

Show that is not Eulerian.

In fact, it contains no Euler trail.

Euler - theorems
1. A connected graph G is Eulerian if and only if G is connected
and has no vertices of odd degree

2. A connected graph G is has an Euler trail from node a to

some other node b if and only if G is connected and a  b are
the only two nodes of odd degree