Discrete Mathematics

(CSE 0611101)

Graphs: Chapter 9

Md. Morshed Ali

Lecturer
Uttara University
1
 What is a Graph?
• Definition1: 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 end points.
• An edge is said to connect its endpoints.
• Note: The set of vertices V of a graph may be infinite.
A graph with an infinite vertex set is called an infinite
graph. A graph with a finite vertex set is called a
finite graph. [ We will consider only finite graphs]
2
 Graph Terminology : Different Types of Graphs

• Simple Graph: An undirected graph with no multiple

edges or loops is called a simple graph.

• Multigraph: An undirected graph that may contain

multiple edges connecting the same vertices but no
loops.

• Pseudograph: An undirected graph that may contain

multiple edges and loops is called a pseudograph.

3
 Graph Terminology : Different Types of Graphs

• Simple Directed graph: When a directed graph has no loops

and has no multiple directed edges, it is called a simple
directed graph.
• Directed multigraph: A graph with directed edges that may
contain multiple directed edges is called a directed
multigraph.
• Mixed Graph: A graph with both directed and undirected
edges is called a mixed graph. A mixed graph may contain
loop(s).
• Loop: An edge that connect a vertex to itself is called a loop.

4
5
6
7
8
9
10
11
 Table 1: Graph Terminology
Type Edges Multiple Edges Loops Allowed?
Allowed?

Simple graph Undirected No No

Multigraph Undirected Yes No

Pseudograph Undirected Yes Yes

Simple directed Directed No No

graph

Directed Multigraph Directed Yes Yes

Mixed graph Directed and Yes Yes

Undirected

12
 Directed Graph
• Definition 2: A directed graph(or digraph) (V,E)
consists of a nonempty set of vertices V and a set of
directed edges E.
• Each directed 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.

13
 9.2 Graph Terminology and
Special Types of Graphs
• Basic terminology
• Adjacent vertices
• Degree of a vertex
– In-degree of a vertex
– Out-degree of a vertex
• Isolated vertex
• Pendant vertex
• The Handshaking Theorem
• Some Special Simple Graphs
• Bipartite Graphs

14
 Basic Terminology
• Definition 1: Two vertices u and v in an undirected
graph G are called adjacent (or neighbors) in G if u
and v are endpoints of an edge of G.
• If e is associated with {u, v}, the edge e is called
incident with the vertices u and v.
• The edge e is also said to connect u and v.
• The vertices u and v are called endpoints of an edge
associated with {u, v}.

15
 Basic Terminology
• Definition 3: 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).

16
 Basic Terminology

• Isolated vertex: A vertex of degree zero is called

isolated.

• Pendant vertex: A vertex is pendant if and only if it

has degree one.

17
 Example 1 (p.598)
• Example 1 (p.598): What are the degrees of the vertices in the graphs G
and H?

Solution:
G: deg(a) = 2, deg(b) = deg(c)= deg(f)=4, deg(d)=1, deg(e) = 3,
and deg(g)= 0
H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.

18
 The Handshaking Theorem
• Theorem 1(The Handshaking Theorem):
Let G = (V,E) be an undirected graph with e edges.
Then

2e = deg(v)

Note: This applies even if multiple edges and loops are present

19
 Example 2
• Example 2 (p.599): How many edges are there
in a graph with 10 vertices each of degree six?

• Solution: Because the sum of the degrees of

the vertices is 6.10 = 60, it follows that 2e=60.
Therefore, e = 30

20
 Theorem 2 (p.599)
• Theorem 2: An undirected graph has an even
number of vertices of odd degree.

• Example: If a graph has 5 vertices, can each vertex

have degree 3?
• Solution: This is not possible by the Handshaking
theorem, because the sum of the degrees of the
vertices 3.5 = 15 is odd.

21
 Initial vertex & Terminal Vertex
• Definition 3: When (u, v) is an edge of the graph G
with directed edges, u is said to be adjacent to v and
v is said to be adjacent from u.
• The vertex u is called the initial vertex of (u, v) and v
is called the terminal/end vertex of (u, v).
• The initial vertex and terminal vertex of a loop are
the same.

22
 In-degree & Out-degree of a vertex
• Definition 4: In a graph with directed edges the
in-degree of a vertex v, denoted by deg–(v), is the
number of edges with v as their terminal vertex.
The out-degree of v, denoted by deg+(v), is the
number of edges with v as their initial vertex.

• Note: A loop at a vertex contributes 1 to both the

in-degree and the out-degree of this vertex.

23
Example: In-degree & Out-degree of a vertex

 Question: What are in-degrees and out-degrees of

all the vertices in the graph below?

1 3

24
Example: In-degree & Out-degree of a vertex

Solution:
deg-(1) = 0
deg-(2) = 3
deg-(3) = 4 2

deg+(1) = 2 1 3

deg+(2) = 3
deg+(3) = 2
• Practice Yourself: Example 4 (p.600)

25
 Theorem 3
• Theorem 3:Let G = ( V, E ) be a graph with directed
edges. Then

deg–(v) = deg+(v) = |E|

 Handshaking Theorem for directed graph

26
Some Special Simple Graphs: Complete Graph(Kn)

• The complete graph on n vertices, denoted by Kn, is

the simple graph that contains exactly one edge
between each pair of distinct vertices.
• The graph , for n = 1, 2, 3, 4, 5, 6 are displayed in the
following figure:

27
 Some Special Simple Graphs: Cycles(Cn)

• The Cycle Cn, n>=3, consists of n vertices v1, v2, ….vn

and edges {v1 , v2 }, {v2, v3}, …. {vn-1, vn }, and {vn, v1 }
• The cycles for C3 , C4 , C5 , and C6 are displayed in the
following figure:

28
 Some Special Simple Graphs: Wheels(Wn)

• We obtain the Wheel (Wn) when we add an additional vertex

to the Cycle Cn , for n>=3, and connect this new vertex to each
of the n vertices in Cn , by new edges.
– The wheel Wn is just a cycle graph with an extra vertex in
the middle
• The Wheels W3 , W4 , W5 are displayed in the figure below:

29
 Some Special Simple Graphs: n-Cubes(Qn)

• The n-dimensional hypercube, or n-cube, denoted by Qn, is

the graph that has vertices representing the 2n bit strings of
length n.
– Two vertices are adjacent iff the bit strings that they represent differ in
exactly one bit position.
– The graphs Q1, Q2 , and Q3are displayed in the following figure:

30
 Bipartite graphs

• Definition 5: A simple graph G is called bipartite if its

vertex set 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 in V2 .
• Note: If each vertex of V1 is connected to each vertex
of V2, then it is called complete bipartite graph and it
is denoted by Km,n where m is the number of vertices
in V1 and n is the number of vertices in V2.

31
Bipartite graphs

32
Example 11(p. 603): Are the graphs H and H are
Bipartite?

33