CHAPTER 1:

BASIC CONCEPTS IN GRAPH THEORY

Discrete Mathematics 2

Lecturer: Nguyen Kieu Linh

Posts and Telecommunications Institute of Technology

Hanoi, 2023

http://www.ptit.edu.vn
Graph Denitions 1-2

Contents

1 Graph Denitions
Graphs
Undirected graph
Directed graph

2 Basic terminologies in undirected graphs

3 Basic terminologies in directed graphs

4 Some special types of graphs

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-3

Contents

1 Graph Denitions
Graphs
Undirected graph
Directed graph

2 Basic terminologies in undirected graphs

3 Basic terminologies in directed graphs

4 Some special types of graphs

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-4

Graphs
Denition
A graph G = hV , E i 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 endpoints . An edge is said to
connect its endpoints.

Figure: A Computer Network.

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-5

Contents

1 Graph Denitions
Graphs
Undirected graph
Directed graph

2 Basic terminologies in undirected graphs

3 Basic terminologies in directed graphs

4 Some special types of graphs

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-6

Some types of Graphs

> Undirected graph

? Undirected Simple Graph

? Undirected Multigraph

? Undirected Pseudograph

> Directed graph

? Directed Simple Graph

? Directed Multigraph

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-7

Undirected Simple Graph

Undirected simple graph G = hV , E i:
? V is the set of vertices
? E is the set of edges, consisting of unordered pairs of two
distinct vertices in V
? There is at most one edge connecting two vertices.

Figure: Undirected Simple Graph.

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-8

Undirected Multigraph
Undirected multigraph G = hV , E i:
? V is the set of vertices
? E is the set of edges, consisting of unordered pairs of two
distinct vertices in V
? e1 , e2 ∈ E are called multiple edges if they connect the same
two vertices, e1 = (u, v ), e2 = (v , u).

Figure: Undirected multigraph.

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-9

Undirected Pseudograph
Undirected Pseudograph G = hV , E i:
? V is the set of vertices
? E is the set of edges, consisting of unordered pairs of two
vertices (maybe the same) in V
? The graph includes edges that connect a vertex to itself. Such
edges are called loops , and sometimes we may even have more
than one loop at a vertex.

Figure: Undirected Pseudograph.

Discrete Mathematics 2  Nguyen Kieu Linh
Graph Denitions 1-10

Contents

1 Graph Denitions
Graphs
Undirected graph
Directed graph

2 Basic terminologies in undirected graphs

3 Basic terminologies in directed graphs

4 Some special types of graphs

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-11

Directed Simple Graph

Directed Simple Graph G = hV , E i:
? V is the set of vertices
? E is the set of directed edges (or arcs, arrows) , consisting of
ordered pairs of two distinct vertices in V
? There is at most one directed edges (or arcs) from a vertex u
to another one v . The directed edge associated with the
ordered pair (u, v ) is said to start at u and end at v.

Figure: Directed Simple Graph.

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-12

Directed Multigraph
Directed Multigraph G = hV , E i:
? V is the set of vertices
? E is the set of directed edges (or arcs) , consisting of ordered
pairs of two distinct vertices in V
? e1 , e2 ∈ E are called multiple directed edges if they connect
the same two vertices, e1 = (u, v ), e2 = (v , u).

Figure: Directed Simple Graph.

Discrete Mathematics 2  Nguyen Kieu Linh

Graph Denitions 1-13

Convention

? We will focus on Undirected Simple Graph and Directed

Simple Graph

? Undirected Graph means Undirected Simple Graph

? Directed Graph means Directed Simple Graph

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-14

Contents

1 Graph Denitions
Graphs
Undirected graph
Directed graph

2 Basic terminologies in undirected graphs

3 Basic terminologies in directed graphs

4 Some special types of graphs

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-15

Vertex Degree

Denition
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 e of G.
Such an edge e is called incident with the vertices u and v and e is
said to connect u and v.

Denition
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 ).

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-16

Vertex Degree
Example
What are the degrees in the graphs G and H displayed in following
gure?

? A vertex of degree zero is called isolated .

? A vertex is pendant if and only if it has degree one.

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-17

Vertex Degree

Theorem
? Let G = hV , E i be an undirected graph with m edges. Then
X
2m = deg (v )
v ∈V

? An undirected graph has an even number of vertices of odd

degree.

Example
How many edges are there in a graph with 10 vertices each of
degree six?

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-18

Path and Circuit

? A path with length n from vertex u to vertex v in undirected
graph G = hV , E > is sequence x0 , x1 , . . . , xn−1 , xn in which n
is a positive integer, x0 = u, xn = v , (xi , xi+1 ) ∈ E ,
i = 0, 1, 2, . . . , n − 1.
? The above path can be represented as a sequence of edges
(x0 , x1 ) (x1 , x2 ) , . . . , (xn−1 , xn ).
? u is the starting point and v is the ending point of the path
? A circuit is a path ending at the starting point (u = v )
? A path or a circuit is said to be simple if there is no repetition
of edges

? A cycle is a simple circuit with no repeated vertices other than

the rst and last ones

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-19

Path and Circuit

Example
? a, d, c, f , e is a simple path with length 4

? d, e, c, b is not a path because (e, c) is not an edge

? b, c, f , e, b is a circuit with length 4

? Path with length 5 : a, b, e, d, a, b is not simple because (a, b)

appears twice

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-20

Connected Graph
Denition
? An undirected graph is said to be connected if there is a path
between every pair of vertices

? If is not connected, G consists of several connected subgraphs

(two subgraphs do not share any vertex)
• Each such subgraph is called a connected component of G .
• An undirected graph is connected if and only if it has only one
connected component

Theorem
In an undirected graph, if there exist a vertex v ∈V such that
there is a path from v to all the other vertices ofV, the graph is
connected.

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-21

Example

How many connected components are there in graph G?

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in undirected graphs 2-22

Bridge and Cut Vertex

Denition
In an undirected graph, a bridge is an edge of the graph whose
deletion increases its number of connected components. A cut
vertex is a vertex whose deletion (with its boundary edges)
increases its number of connected components.
Example
Find the bridges and cut vertices in the graph below

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in directed graphs 3-23

Contents

1 Graph Denitions
Graphs
Undirected graph
Directed graph

2 Basic terminologies in undirected graphs

3 Basic terminologies in directed graphs

4 Some special types of graphs

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in directed graphs 3-24

In-degree and Out-degree

Denition
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 or end vertex of (u, v ).
Denition
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.

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in directed graphs 3-25

In-degree and Out-degree

Example
Find the in-degree and out-degree of each vertex in the following
graph with directed edges.

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in directed graphs 3-26

In-degree and Out-degree

Theorem
For any directed graph G = hV , E i, we have
X X
deg+ (v ) = deg− (v ) = |E |.
v ∈V v ∈V

Notation
? Many properties of directed graphs do not depend on
directions. In some cases, we can ignore the directions on
directed edges.
? The undirected graph receiving by removing directions on
directed edges is called the corresponding undirected graph.

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in directed graphs 3-27

Path and Circuit

? A path with length n from vertexu to vertex v in directed

graph G = hV , E i . is sequence x0 , x1 , . . . , xn−1 , xn in which n
is a positive integer, x0 = u, xn = v , (xi , xi+1 ) ∈ E ,
i = 0, 1, 2, . . . , n − 1.
? The above path can be represented as a sequence of edges
(x0 , x1 ) (x1 , x2 ) , . . . , (xn−1 , xn ).
? u is the starting point and v is the ending point of the path

? A circuit is a path ending at the starting point (u = v )

? A path or a circuit is said to be simple if there is no repetition
of directed edges.

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in directed graphs 3-28

Strongly Connected Graph, Weakly Connected Graph

Denition
? Directed graph G = hV , E i is said to be strongly connected if
there is a path between every pair of vertices.

? Directed graph G = hV , E i is said to be weakly connected if

its corresponding undirected graph is connected.

Discrete Mathematics 2  Nguyen Kieu Linh

Basic terminologies in directed graphs 3-29

Orientation

Denition
An orientation of an undirected graph is an assignment of a
direction to each edge, turning the initial graph into a directed
graph. A strong orientation is an orientation that results in a
strongly connected graph.

Theorem
For any undirected graph G = hV , E i, there exists a strong
orientation on G if and only if all its edges are not bridge.

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-30

Contents

1 Graph Denitions
Graphs
Undirected graph
Directed graph

2 Basic terminologies in undirected graphs

3 Basic terminologies in directed graphs

4 Some special types of graphs

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-31

Complete Graph

Denition
? Complete graph n vertices, denoted by Kn , is a simple
undirected graph that exists an edge connecting between two
every vertices
n(n−1)
? Number of edges:
2

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-32

Cycle Graph

Denition
Cycle Graph Cn , n ≥ 3, consists of n vertices

{v2 , v3 }, ..., {vn−1 , vn }, and {vn , v1 }.

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-33

Wheel Graph

Denition
Wheel graph n vertices, denoted by Wn is a graph formed by
connecting a single vertex to all vertices of a cycle graph Cn−1 .

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-34

Bipartite Graph (Bigraph)

Denition
Bigraph G = hV , E i is a graph whose vertices can be divided into
two disjoint sets X and Y and such that every edge connects a
vertex in to one in, i.e. (x, y ), in which x ∈ X , y ∈ Y

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-35

Exercises

Exercise 1. Determine the degree of each vertex in the below

undirected graph

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-36

Exercises

Exercise 2. Determine the in-degree and out-degree of each vertex

in the below directed graph

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-37

Exercises

Exercise 3. Determine the degree of each vertex in the below

undirected graph

Discrete Mathematics 2  Nguyen Kieu Linh

Some special types of graphs 4-38

Exercises

Exercise 4. Determine the in-degree and out-degree of each vertex

in the below directed graph

Discrete Mathematics 2  Nguyen Kieu Linh