1 Notations EN

Posts and Telecommunications Institute of Technology
Faculty of Information Technology 1
Discrete Mathematics 2
Basic Concepts in Graph Theory
Ngo Xuan Bach

Contents
 Graph Definitions
 Basic Terms in Undirected Graphs
 Basic Terms in Directed Graphs
 Some Special Types of Graphs
2 http://www.ptit.edu.vn
Undirected Simple Graph
 Definition 1: Undirected simple graph 𝐺 = < 𝑉, 𝐸 >:
o 𝑉 is the set of vertices
o 𝐸 is the set of edges, consisting of unordered pairs of two distinct
vertices in 𝑉
o There is at most one edge connecting two vertices
Undirected Multigraph
 Definition 2: Undirected multigraph 𝐺 = < 𝑉, 𝐸 >:
o 𝐸 is the set of edges, consisting of unordered pairs of two distinct
vertices in 𝑉
o 𝑒1 ∈ 𝐸, 𝑒2 ∈ 𝐸 are called multiple edges if they connect the same
two vertices, 𝑒1 = 𝑢, 𝑣 , 𝑒2 = 𝑢, 𝑣
Undirected Pseudograph
 Definition 3: Undirected pseudograph 𝐺 = < 𝑉, 𝐸 >
o 𝐸 is the set of edges, consisting of unordered pairs of two (maybe
the same) vertices in 𝑉
Directed Simple Graph
 Definition 4: Directed simple graph 𝐺 = < 𝑉, 𝐸 >:
o 𝐸 is the set of edges (arrows), consisting of ordered pairs of two
distinct vertices in 𝑉
o There is at most one edge (arrow) from a vertex to another one
Directed Multigraph
 Definition 5: Directed multigraph 𝐺 = < 𝑉, 𝐸 >:
o 𝐸 is the set of edges (arrows), consisting of ordered pairs of two
distinct vertices in 𝑉
o 𝑒1 ∈ 𝐸, 𝑒2 ∈ 𝐸 are called multiple arrows if they connect the same
two vertices, 𝑒1 = 𝑢, 𝑣 , 𝑒2 = 𝑢, 𝑣

Convention
 We will focus on Undirected Simple Graph and Directed
Simple Graph
 “Undirected Graph” means “Undirected Simple Graph”
 “Directed Graph” means “Directed Simple Graph”
Contents
Vertex Degree
 Definition 1: Two vertices 𝑢 and 𝑣 of undirected graph
𝐺 =< 𝑉, 𝐸 > are said to be adjacent if there is an edge
connecting them. If 𝑒 = (𝑢, 𝑣) is an edge of undirected
graph 𝐺, e is said to be incident to 𝑢 and 𝑣; two vertices
𝑢 and 𝑣 are said to be the endpoints of edge 𝑒.
 Definition 2: The degree of a vertex 𝑣 of an undirected

graph, denoted by deg(𝑣) , is the number of edges
incident to the vertex.
Example
 deg(𝑎) = 2, deg(𝑏) = deg(𝑐) = deg(𝑓) = 4;
 deg(𝑒) = 3, deg(𝑑) = 1, deg(𝑔) = 0.
 An isolated vertex is a vertex with degree zero (e.g. 𝑔)

 A leaf vertex (also terminal vertex) is a vertex with
degree one (e.g. 𝑑)
Sum of Degrees of Vertices Theorem
 Theorem 1: Suppose an undirected graph 𝐺 =< 𝑉, 𝐸 >
has m edges, then we have: σ𝑣∈𝑉 deg 𝑣 = 2𝑚.
 Proof: for each edge 𝑒 = (𝑢, 𝑣), degree is counted one
time in deg(𝑢) and one time in deg(𝑣). Therefore, sum of
the degrees of the vertices equals twice the number of
edges.
 Corollary 1: For any undirected graph, the number of

vertices with odd degree is even.
Path, Circuit
 Definition 1: Path with length 𝑛 from vertex 𝑢 to vertex 𝑣 in
undirected graph 𝐺 =< 𝑉, 𝐸 > is sequence 𝑥0 , 𝑥1 , . . . , 𝑥𝑛−1 , 𝑥𝑛 ,
in which 𝑛 is a positive integer, 𝑥0 = 𝑢, 𝑥𝑛 = 𝑣, (𝑥𝑖 , 𝑥𝑖+1 ) ∈ 𝐸,
𝑖 = 0, 1, 2, . . . , 𝑛 − 1.
 The above path can be represented as a sequence of
edges (𝑥0 , 𝑥1 )(𝑥1 , 𝑥2 ) , . . . , (𝑥𝑛−1 , 𝑥𝑛 ).
 𝑢 is the starting point and 𝑣 is the ending point of the path
 A circuit is a path ending at the starting point (𝑢 = 𝑣)

 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 first and last ones
Example
 𝑎, 𝑑, 𝑐, 𝑓, 𝑒 is a simple path with length 4
 𝑑, 𝑒, 𝑐, 𝑏 is not a path because (𝑒, 𝑐) is not an edge
 𝑏, 𝑐, 𝑓, 𝑒, 𝑏 is a circuit with length 4
 Path with length 5 𝑎, 𝑏, 𝑒, 𝑑, 𝑎, 𝑏 is not simple because
(𝑎, 𝑏) appears twice
Connected Graph
 Definition 2: An undirected graph is said to be
connected if there is a path between every pair of
vertices
 If 𝐺 =< 𝑉, 𝐸 > is not connected, 𝐺 consists of several

connected subgraphs (two subgraphs do not share any
vertex)
o Each such subgraph is called a connected component of 𝐺
o An undirected graph is connected if and only if it has only one
connected component
 In an undirected graph, if there exist a vertex 𝑢 ∈ 𝑉 such

that there is a path from 𝑢 to all the other vertices of 𝑉,
the graph is connected
Example
 Undirected graph 𝐺 consists of 3 connected components
Bridge, Cut Vertex
 Definition 3: 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.
 Examples: (5,9) and (5,10) are bridges; 5,6 are cut
vertices
Contents
Indegree and Outdegree
 Definition 1: If 𝑒 = (𝑢, 𝑣) is an arrow of directed graph
𝐺, then 𝑢 and 𝑣 is said to be adjacent. Vertex 𝑣 is called
the head end and vertex 𝑢 is called the tail end of arrow
(𝑢, 𝑣).
 Definition 2: In a directed graph, the number of arrows

ending at a vertex is called the indegree of the vertex
(denoted by 𝑑𝑒𝑔− (𝑣)) and the number of arrows starting
at a vertex is its outdegree (denoted by 𝑑𝑒𝑔+ (𝑣)).
Example
 𝑑𝑒𝑔+ 𝑎 = 2, 𝑑𝑒𝑔+ 𝑏 = 2, 𝑑𝑒𝑔+ 𝑐 = 0,
𝑑𝑒𝑔+ (𝑑) = 2, 𝑑𝑒𝑔+ (𝑒) = 1.
 𝑑𝑒𝑔− 𝑎 = 1, 𝑑𝑒𝑔− 𝑏 = 1, 𝑑𝑒𝑔− 𝑐 = 2,
𝑑𝑒𝑔− (𝑑) = 2, 𝑑𝑒𝑔− (𝑒) = 1.
Sum of Indegrees/Outdegrees
of Vertices Theorem
 Theorem 1: For any directed graph 𝐺 =< 𝑉, 𝐸 >, we
have: σ𝑣∈𝑉 𝑑𝑒𝑔+ (𝑣) = σ𝑣∈𝑉 𝑑𝑒𝑔− (𝑣) = |𝐸|.
 Proof: Each arrow (𝑢, 𝑣) is counted one time in 𝑑𝑒𝑔− 𝑣
and one time in 𝑑𝑒𝑔+ 𝑣 .
 Notes:
o Many properties of directed graphs do not depend on directions.
In some cases, we can ignore the directions on arrows.
o The undirected graph receiving by removing directions on arrows
is called the corresponding undirected graph.
Path, Circuit
 Definition 1: Path with length 𝑛 from vertex 𝑢 to vertex
𝑣 in directed graph 𝐺 =< 𝑉, 𝐸 > is sequence
𝑥0 , 𝑥1 , . . . , 𝑥𝑛−1 , 𝑥𝑛 , in which 𝑛 is a positive integer, 𝑥0 =
𝑢, 𝑥𝑛 = 𝑣, (𝑥𝑖 , 𝑥𝑖+1 ) ∈ 𝐸, 𝑖 = 0, 1, 2, . . . , 𝑛 − 1.
 The above path can be represented as a sequence of
arrows (𝑥0 , 𝑥1 )(𝑥1 , 𝑥2 ) , . . . , (𝑥𝑛−1 , 𝑥𝑛 )
 𝑢 is the starting point and 𝑣 is the ending point of the
path
 A circuit is a path ending at the starting point (𝑢 = 𝑣)

 A path or a cycle is said to be simple if there is no
repetition of arrows
Strongly Connected Graph,
Weakly Connected Graph
Definition 2: Directed graph 𝐺 =< 𝑉, 𝐸 > is said to be
strongly connected if there is a path between every pair of
vertices.
Definition 3: Directed graph 𝐺 =< 𝑉, 𝐸 > is said to be
weakly connected if its corresponding undirected graph is
connected.
Orientation
 Definition 4: 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 1: For any undirected graph 𝐺 =< 𝑉, 𝐸 >,

there exists a strong orientation on 𝐺 if and only if all its
edges are not bridge.
Contents
Complete Graph
 Complete graph 𝑛 vertices, denoted by 𝐾𝑛 , is a simple
undirected graph that exists an edge connecting between
two every vertices
𝑛(𝑛−1)
 Number of edges:
2
Cycle Graph
 Cycle graph 𝑛 vertices, denoted by 𝐶𝑛 (𝑛 ≥ 3) is a
simple undirected graph consisting of edges
(1,2), (2,3), … , (𝑛 − 1, 𝑛), (𝑛, 1)
Wheel Graph
 Wheel graph 𝑛 vertices, denoted by 𝑊𝑛 is a graph
formed by connecting a single vertex to all vertices of a
cycle graph 𝐶𝑛−1 .
Bipartite Graph (Bigraph)
 Bigraph 𝐺 =< 𝑉, 𝐸 > is a graph whose vertices can be
divided into two disjoint sets 𝑋 and 𝑌 and such that
every edge connects a vertex in to one in, i.e. (𝑥, 𝑦), in
which 𝑥 ∈ 𝑋 and 𝑦 ∈ 𝑌.
Exercise 1
 Determine the degree of each vertex in the below
undirected graph
2 5
1 7
4
3 6
Exercise 2
 Determine the indegree and outdegree of each vertex in
the below directed graph
2 5
1 7
4
3 6

1 Notations EN

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

1 Notations EN

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

1 Notations EN

Uploaded by

Copyright:

Available Formats

Posts and Telecommunications Institute of Technology

Faculty of Information Technology 1

Basic Concepts in Graph Theory

Ngo Xuan Bach

 Definition 2: The degree of a vertex 𝑣 of an undirected

 An isolated vertex is a vertex with degree zero (e.g. 𝑔)

 Corollary 1: For any undirected graph, the number of

 A circuit is a path ending at the starting point (𝑢 = 𝑣)

 If 𝐺 =< 𝑉, 𝐸 > is not connected, 𝐺 consists of several

 In an undirected graph, if there exist a vertex 𝑢 ∈ 𝑉 such

 Definition 2: In a directed graph, the number of arrows

 A circuit is a path ending at the starting point (𝑢 = 𝑣)

 Theorem 1: For any undirected graph 𝐺 =< 𝑉, 𝐸 >,

You might also like