Graph

Lecture 15

1
 Graph

Definition: A graph G = (V, E) consists of a nonempty set

V of vertices (or nodes) and a set E of edges. Each edge
has either one or two vertices associated with it, called its
endpoints. An edge is said to connect its endpoints.

Example

2
 Terminology
In a simple graph each edge connects two different
vertices and no two edges connect the same pair of
vertices.

Multigraphs may have multiple edges connecting the

same two vertices. When m different edges connect the
vertices u and v, we say that {u,v} is an edge of
multiplicity m.

• An edge that connects a vertex to itself is called a loop.

• A pseudograph may include loops, as well as multiple

edges connecting the same pair of vertices.
3
 Directed graph
Definition: A directed graph (or digraph) G = (V, E) consists of a
nonempty set V of vertices (or nodes) and a set E of directed edges
(or arcs). Each edge is associated with an ordered pair of vertices.
The directed edge associated with the ordered pair (u,v) is said to
start at u and end at v.

4
 Directed graph
A simple directed graph has no loops and no multiple edges.
Example:

• A directed multigraph may have multiple directed edges.

When there are m directed edges from the vertex u to the
vertex v, we say that (u,v) is an edge of multiplicity m.

Example:
• multiplicity of (a,b) is ?
• and the multiplicity of (b,c) is ?

5
 Directed graph
A simple directed graph has no loops and no multiple edges.
Example:

• A directed multigraph may have multiple directed edges.

When there are m directed edges from the vertex u to the
vertex v, we say that (u,v) is an edge of multiplicity m.

Example:
• multiplicity of (a,b) is ? 1
• and the multiplicity of (b,c) is ? 2

6
 Undirected graph
Definition 1. Two vertices u, v in an undirected graph G are
called adjacent (or neighbors) in G if there is an edge e between u and
v. Such an edge e is called incident with the vertices u and v
and e is said to connect u and v.

Definition 2. The set of all neighbors of a vertex v of G = (V, E),

denoted by N(v), is called the neighborhood of v. If A is a subset
of V, we denote by N(A) the set of all vertices in G that are adjacent
to at least one vertex in A. So,

Definition 3. The degree of a vertex in a undirected graph is the

number of edges incident with it, except that a loop at a vertex
contributes two to the degree of that vertex. The degree of the
vertex v is denoted by deg(v).

7
 Undirected graph
Example: What are the degrees and neighborhoods of the vertices in
the graphs G?

Solution:
G: deg(a) = 2,
deg(b) = deg(c) = deg(f ) = 4,
deg(d ) = 1,
deg(e) = 3,
deg(g) = 0.
N(a) = {b, f }, N(b) = {a, c, e, f }, N(c) = {b, d, e, f },
N(d) = {c}, N(e) = {b, c , f }, N(f) = {a, b, c, e}, N(g) = Ø . 8
 Undirected graph
Example: What are the degrees and neighborhoods of the vertices in
the graphs H?

Solution:
H: deg(a) = ?, deg(b) = deg(e) = ?, deg(c) = 1, deg(d) = ?.
N(a) = {b, d, e}, N(b) = {a, b, c, d, e}, N(c) = {b},
N(d) = {a, b, e}, N(e) = {a, b ,d}.
9
 Undirected graph
Example: What are the degrees and neighborhoods of the vertices in
the graphs H?

Solution:
H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.
N(a) = {b, d, e}, N(b) = {a, b, c, d, e}, N(c) = {b},
N(d) = {a, b, e}, N(e) = {a, b ,d}.
10
 Undirected graph
Theorem 1 : If G = (V,E) is an undirected graph with m edges, then

2m   deg(v)
Proof: vV

Each edge contributes twice to the degree count of all vertices.

Hence, both the left-hand and right-hand sides of this equation
equal twice the number of edges.

11
 Undirected graph
Theorem 2: An undirected graph has an even number of vertices of odd
degree.

Proof: Let V1 be the vertices of even degree and V2 be the vertices

of odd degree in an undirected graph G = (V, E) with m edges.
Then

2m   deg(v)   deg(v)   deg(v)

vV vV1 vV2
must be This sum must be even because 2m
even since is even and the sum of the degrees
deg(v) is of the vertices of even degrees is
even for also even. Because this is the sum
each v ∈ V1 of the degrees of all vertices of odd
degree in the graph, there must be
an even number of such vertices.

12
 Directed graph
Definition: An directed graph G = (V, E) consists of V, a
nonempty set of vertices (or nodes), and E, a set of directed edges
or arcs. Each edge is an ordered pair of vertices. The directed
edge (u,v) is said to start at u and end at v.

Definition: Let (u,v) be an edge in G. Then u is the initial vertex

of this edge and is adjacent to v and v is the terminal (or end)
vertex of this edge and is adjacent from u. The initial and terminal
vertices of a loop are the same.

13
 Directed graph
Definition: The in-degree of a vertex v, denoted deg- (v), is
the number of edges which terminate at v. The out-degree of v,
denoted deg+(v), is the number of edges with v as their initial
vertex. Note that a loop at a vertex contributes 1 to both the indegree
and the out-degree of the vertex

Example: Assume graph G

deg- (a)=2, deg- (b)=2, deg- (c)=3,

deg- (d)=?, deg- (e)=?, deg- (f)=?

14
 Directed graph
Definition: The in-degree of a vertex v, denoted deg- (v), is
the number of edges which terminate at v. The out-degree of v,
denoted deg+(v), is the number of edges with v as their initial
vertex. Note that a loop at a vertex contributes 1 to both the indegree
and the out-degree of the vertex

Example: Assume graph G

deg- (a)=2, deg- (b)=2, deg- (c)=2,

deg- (d)=2, deg- (e)=3, deg- (f)=0

15
 Directed graph
Definition: The in-degree of a vertex v, denoted deg- (v), is
the number of edges which terminate at v. The out-degree of v,
denoted deg+(v), is the number of edges with v as their initial
vertex. Note that a loop at a vertex contributes 1 to both the indegree
and the out-degree of the vertex

Example: Assume graph G

Deg+ (a)=4, deg+ (b)=1, deg+ (c)=2,

deg+ (d)=?, deg+ (e)=?, deg+ (f)=?

16
 Directed graph
Definition: The in-degree of a vertex v, denoted deg- (v), is
the number of edges which terminate at v. The out-degree of v,
denoted deg+(v), is the number of edges with v as their initial
vertex. Note that a loop at a vertex contributes 1 to both the indegree
and the out-degree of the vertex

Example: Assume graph G

Deg+ (a)=4, deg+ (b)=1, deg+ (c)=2,

deg+ (d)=2, deg+ (e)=3, deg+ (f)=0

17
 Directed graph
Theorem: Let G = (V, E) be a graph with directed edges. Then:

| E |  deg  (v)   deg  (v)

vV vV

Proof:
The first sum counts the number of outgoing edges over all vertices
and the second sum counts the number of incoming edges over all
vertices. It follows that both sums equal the number of edges in the
graph.

18
 Complete graph
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of distinct
vertices.

19
 A Cycle
A cycle Cn for n ≥ 3 consists of n vertices v1, v2 ,⋯ , vn, and edges
{v1, v2}, {v2, v3} ,⋯ , {vn-1, vn}, {vn, v1}.

20
 N-dimensional hypercube
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n
vertices representing all bit strings of length n, where there is an
edge between two vertices that differ in exactly one bit position.

21
 Bipartite Graph
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.

22
 Bipartite Graph
Example: Show that C6 is bipartite.

23
 Bipartite Graph
Example: Show that C6 is bipartite.

Solution: We can partition the vertex set into V1 = {v1,

v3, v5} and V2 = {v2, v4, v6} so that every edge of C6
connects a vertex in V1 and V2 .

24
 Bipartite Graph
Example: Show that C3 is not bipartite.

25
 Bipartite Graph
Example: Show that C3 is not bipartite.

Solution: If we divide the vertex set of C3 into two

nonempty sets, one of the two must contain two vertices.
But in C3 every vertex is connected to every other
vertex. Therefore, the two vertices in the same partition
are connected. Hence, C3 is not bipartite.

26
 Complete Bipartite Graph
Definition: A complete bipartite graph Km,n is a graph that
has its vertex set partitioned into two subsets V1 of size m
and V2 of size n such that there is an edge from every
vertex in V1 to every vertex in V2.

Example: We display four complete bipartite graphs here.

27
 Subgraph
Definition: A subgraph of a graph G = (V,E) is a graph
(W,F), where W ⊂ V and F ⊂ E. A subgraph H of G is a
proper subgraph of G if H ≠ G.

Example: K5 and one of its subgraphs.

28
 Subgraph
Definition: Let G = (V, E) be a simple graph. The subgraph
induced by a subset W of the vertex set V is the graph
(W,F), where the edge set F contains an edge in E if and
only if both endpoints are in W.

Example: K5 and the subgraph induced by W = {a,b,c,e}.

29
 Union of Graph
Definition: The union of two simple graphs G1 = (V1, E1)
and G2 = (V2, E2) is the simple graph with vertex set V1 ⋃
V2 and edge set E1 ⋃ E2. The union of G1 and G2 is
denoted by G1 ⋃ G2.

Example:

30
 Representation: Adjacency List
Definition: An adjacency list can be used to represent a
graph with no multiple edges by specifying the vertices that
are adjacent to each vertex of the graph.

Example:
An adjacency list for a simple graph
vertex Adjacent vertex
a b, c, e
b a
c a, d, e
d c, e
e a, d, c
31
 Representation: Adjacency List
Definition: An adjacency list can be used to represent a
graph with no multiple edges by specifying the vertices that
are adjacent to each vertex of the graph.

Example:
An adjacency list for a directed graph
vertex Adjacent vertex
a b, c, d, e
b b, d
c a, c, e
d
e b, c, d
32
 Adjacency Matrix
Definition: Suppose that G = (V, E) is a simple graph where
|V| = n. Arbitrarily list the vertices of G as v 1, v2, … , vn. The
adjacency matrix AG of G, with respect to the listing of
vertices, is the n × n zero-one matrix with 1 as its (i, j)th
entry when vi and vj are adjacent, and 0 as its (i, j)th entry
when they are not adjacent.

Example:
0 1 1 1
1 0 1 0

1 1 0 0
 
1 0 0 0
33
 Adjacency Matrix
Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, i)th position of
the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or if
multiple loops are present at the same vertex), the (i, j)th entry equals
the number of edges connecting the pair of vertices.

Example: The adjacency matrix of the pseudograph shown here using

the ordering of vertices a, b, c, d.

0 3 0 2
3 0 1 1 

0 1 1 2
 
2 1 2 0 34
 Graph Isomorphism
Definition: The simple graphs G1 = (V1, E1) 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 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.

one-to-one correspondence between vertices of the two graphs that

preserves the adjacency relationship

Are the two graph isomorphic?

35
 Graph Isomorphism
Definition: The simple graphs G1 = (V1, E1) 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 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.

Are the two graph isomorphic?

u1 → v 1
u2 → v 4
u3 → v 3
u4 → v 2
f(u1) = v1 and f (u2) = v4, f (u1) = v1 and f (u3) = v3, f (u2) = v4 and f (u4) = v2, 36
and f (u3) = v3 and f (u4) = v2
 Path
A path in a graph is a continuous way of getting
from one vertex to another by using a sequence of
edges.

37
 Path Length
A path of length n in an undirected graph is a
sequence of n edges e1, e2, … ,en such that each
consecutive pair ei , ei+1 share a common vertex.

38
 Path and Cycle
A simple path contains no duplicate edges
(though duplicate vertices are allowed). A cycle
(or circuit) is a path which starts and ends at the
same vertex.

39
 Connectivity
Let G be a dograph. Let u and v be vertices. u
and v are connected to each other if there is a
path in G which starts at u and ends at v. G is said
to be connected if all vertices are connected to
each other.

40
 Connectivity in directed graph
1) Weakly connected : can get from a to b in
underlying undirected graph
2) Strongly connected : there is a path from a to
b AND from b to a in the digraph

Weekly connected strongly connected 41

 Euler Circuit

An Euler circuit in a graph G is a simple circuit

containing every edge of G.

A connected graph contains an Eulerian Circuit if and

only if every vertex has even degree.
42
 Euler Path

An Euler path in G is a simple path containing every

edge of G.

A connected graph contains an Eulerian Path if and

only if exactly 2 vertices have odd degree.

43
 Hamiltonian Circuit Problem

• Hamiltonian Circuit – a simple cycle including all the

vertices of the graph

44
 Hamilton Path
• A Hamilton path of a graph or digraph is a path that
contains each vertex exactly once, except that the end
vertices may be the same.
• A Hamilton circuit (or cycle) is a Hamilton path that is a
cycle.
• Contrast this with an Euler circuit which contains each
edge exactly once.

45
 Review Graph
find the union of the given pair of simple graphs.

46
 Review Graph
determine whether the given graph is connected.

47
 Review Graph
determine whether the graph is bipartite

48
 Review Graph
Determine whether the graphs are isomorphic or not.

49
 Review Graph
determine whether the given graph has an
Euler circuit.

If no Euler circuit exists, determine whether the graph

has an Euler path

50
 Review Graph
determine whether the given graph has a
Hamilton circuit. If it does, find such a circuit.

51
Thank You

52