Basic Graph Terminology in Discrete Mathematics
Discrete
Mathematics
Basic
Graph
Terminology
Part -1
2
Definition
1:
Two
vertices
𝑢
and
𝑣
in an
undirected graph
G
are
called
adjacent
(or
neighbors
) in
G
if
u
and
v
are
endpoints
of
an
edge
𝑒
of
G
.
Such
an
edge
𝑒
is
called
incident
with
the
vertices
𝑢
and
𝑣
and
𝑒
is said
to
connect
𝑢
and
𝑣
.
e
d
g
e
(
𝑢
,
𝑣
)
𝑣
𝑢
3
Definition
2:
The
set
of
all
neighbors
of
a
vertex
𝑣
of
𝐺
=
(𝑉,
𝐸)
,
denoted
by
𝑁(𝑣)
,
is
called
the
neighborhood
of
𝑣
.
If
𝐴
is
a
subset
of
𝑉
,
we
d
e
n
o
te
by
𝑁
(𝐴
)
the
s
e
t
o
f
all
ve
rtic
e
s
in
𝐺
that
are
adjacent
to
at
least
one
vertex
in
𝐴
.
So,
𝑁(𝐴)
=
𝑣∈𝐴
𝑁
𝑣
.
=
𝒃
,
𝒇
=
𝒂,
𝒄
,
𝒆
,
𝒇
=
𝒃
,
𝒅
,
𝒆
,
𝒇
=
𝒄
=
𝒃
,
𝒄
,
𝒇
=
𝒂,
𝒃
,
𝒄
,
𝒆
𝑵
𝒂
𝑵
𝒃
𝑵
𝒄
𝑵
𝒅
𝑵
𝒆
𝑵
𝒇
𝑵
𝐠
=
∅
4
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
)
.
deg
(𝑎)
=
2
deg
(𝑏)
=
4
deg
(𝑐)
=
4
deg
(𝑑)
=
1
deg
(𝑒)
=
3
deg
(𝑓)
=
4
deg
(g)
=
0
5
Isolated:
A
vertex
of
degree
zero
is
called
isolated
.
It
follows
that an
isolated
vertex
is
not
adjacent to
any
vertex.
Vertex
g
is
isolated
.
deg
(𝑎)
=
2
deg
(𝑏)
=
4
deg
(𝑐)
=
4
deg
(𝑑)
=
1
deg
(𝑒)
=
3
deg
(𝑓)
=
4
deg
(g)
=
0
6
Pendant:
A
vertex
is
pendant
if and
only
if it
has
degree
one
.
Vertex
𝑑
is
pendant
.
deg
(𝑎)
=
2
deg
(𝑏)
=
4
deg
(𝑐)
=
4
deg
(𝑑)
=
1
deg
(𝑒)
=
3
deg
(𝑓)
=
4
deg
(g)
=
0
7
Example
1:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
deg
(𝑎)
=
deg
(𝑏)
=
deg
(𝑐)
=
deg
(𝑑)
=
deg
(𝑒)
=
8
Example
1:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
deg
(𝑎)
=
4
deg
(𝑏)
=
6
deg
(𝑐)
=
1
deg
(𝑑)
=
5
deg
(𝑒)
=
6
9
Example
1:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
deg
(𝑎)
=
4
deg
(𝑏)
=
6
deg
(𝑐)
=
1
deg
(𝑑)
=
5
deg
(𝑒)
=
6
Vertex
𝒄
i
s
p
e
n
da
n
t
10
Example
1:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
𝑁(𝑎)
=
𝑁(𝑏)
=
𝑁(𝑐)
=
𝑁(𝑑)
=
𝑁(𝑒)
=
11
Example
1:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
𝑁
(
𝑎
)
=
{𝑏
,
𝑑
,
𝑒
}
𝑁
(
𝑏
)
=
{𝑎
,
𝑏
,
𝑐
,
𝑑
,
𝑒
}
𝑁(𝑐)
=
𝑏
𝑁
(
𝑑
)
=
{𝑎
,
𝑏
,
𝑒
}
𝑁
(
𝑒
)
=
𝑎
,
𝑏
,
𝑑
12
Example
2:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
Number
of
vertices
=
5
Number
of
edges
=
13
13
Example
2:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
deg
(𝑎)
=
deg
(𝑏)
=
deg
(𝑐)
=
deg
(𝑑)
=
deg
(𝑒)
=
14
Example
2:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
deg
(𝑎)
=
6
deg
(𝑏)
=
6
deg
(𝑐)
=
6
deg
(𝑑)
=
5
deg
(𝑒)
=
3
15
Example
2:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
𝑁(𝑎)
=
𝑁(𝑏)
=
𝑁(𝑐)
=
𝑁(𝑑)
=
𝑁(𝑒)
=
16
Example
2:
What
are
the
degrees
and
what
are
the
neighborhoods
of
the
vertices
in
the
following
graph?
𝑁
(
𝑎
)
=
{𝑎
,
𝑏
,
𝑒
}
𝑁
(
𝑏
)
=
{𝑎
,
𝑒
,
𝑑
,
𝑐
}
𝑁
(
𝑐
)
=
𝑏
,
𝑐
,
𝑑
𝑁
(
𝑑
)
=
{𝑒
,
𝑏
,
𝑐
}
𝑁
(
𝑒
)
=
𝑎
,
𝑏
,
𝑑
17
The
Handshaking
Theorem:
Let
𝐺
=
(
𝑉
,
𝐸
) be
undirected
graph
with
E
edges.
Then
2
E
=
deg(𝑣)
𝑣∈𝑉
edge
E
d
g
e
h
a
v
ing
t
w
o
en
d
p
o
in
t
s
a
n
d
a
h
a
n
d
s
h
a
k
e
in
v
o
l
v
ing
two
hands.
18
Example
3:
H
o
w
m
any
e
d
ge
s
are
th
e
re
in
an
undir
e
ct
e
d
g
raph
with
10
vertices
each
of
degree
six?
19
Exa
m
p
l
e
3:
An
s
w
e
r
How
many
edges
are
there
in
a
graph
with
10
vertices
each
of
degree
six?
2
E
=
deg(𝑣)
𝑣∈𝑉
Solution:
Because
the
sum
of
the
degrees
of
the
vertices
is
6
·
10
=
60,
it
follows
that 2
E
=
60.
Therefore,
E
=
30.
20
𝑣
𝑢
Definition
4:
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
).
The
initial
vertex
and
terminal
vertex
of
a
loop
are the
same.
edge
(
u
,
v
)
21
Definition
5:
In
a
graph
with
directed
edges
the
in-degree
of
a
vertex
𝑣
,
denoted
by
deg
−
(𝑣)
,
is the
number
of
edges
with
𝑣
as
their
terminal
vertex.
The
out-degree
of
𝑣
,
denoted
by
deg
+
(𝑣)
,
is the
number
of
edges
with
𝑣
as
their
initial
vertex.
(Note
that a
loop
at a
vertex
contributes
1 to
both
the
in-
degree
and the
out-degree
of
this
vertex.)
22
Example
4:
deg
−
(𝑎)
=
deg
−
(𝑏)
=
deg
−
(𝑐)
=
deg
−
(𝑑)
=
deg
−
(𝑒)
=
deg
−
(𝑓)
=
Number
of
vertices
=
Number
of
edges
=
deg
+
(𝑎)
=
deg
+
(𝑏)
=
deg
+
(𝑐)
=
deg
+
(𝑑)
=
deg
+
(𝑒)
=
deg
+
(𝑓)
=
23
Example
4:
deg
−
(𝑎)
= 2
deg
−
(𝑏)
= 2
deg
−
(𝑐)
= 3
deg
−
(𝑑)
=
2
deg
−
(𝑒)
= 3
deg
−
(𝑓)
=
0
Number
of
vertices
=
6
Number
of
edges
=
12
deg
+
(𝑎)
= 4
deg
+
(𝑏)
= 1
deg
+
(𝑐)
= 2
deg
+
(𝑑)
= 2
deg
+
(𝑒)
= 3
deg
+
(𝑓)
=
0
24
Theorem
3:
25
Example
4:
Recall:
deg
−
(𝑎)
= 2
deg
−
(𝑏)
= 2
deg
−
(𝑐)
= 3
deg
−
(𝑑)
=
2
deg
−
(𝑒)
= 3
deg
−
(𝑓)
=
0
Number
of
vertices
=
6
Number
of
edges
=
12
deg
+
(𝑎)
=
deg
+
(𝑏)
=
deg
+
(𝑐)
=
deg
+
(𝑑)
=
deg
+
(𝑒)
=
deg
+
(𝑓)
=
4
1
2
2
3
0
Exploring the fundamental definitions in graph theory including adjacent vertices, neighborhoods, degrees of vertices, isolated and pendant vertices. Examples are provided to illustrate the concepts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Discrete Mathematics Basic Graph Terminology Part -1
BASIC GRAPH TERMINOLOGY Definition 1: Two vertices ? and ? in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge ? of G. Such an edge ? is called incident with the vertices ? and ? and ? is said to connect ? and ?. edge (?,?) ? ? 2
BASIC GRAPH TERMINOLOGY Definition 2: The set of all neighbors of a vertex ? of ? = (?,?), denoted by ?(?), is called the neighborhood of ?. If ? is a subset of ?, we denote by ?(?) the set of all vertices in ? that are adjacent to at least one vertex in ?. So, ?(?) = ? ?? ? . = ?,? = ?,?,?,? = ?,?,?,? = ? = ?,?,? = ?,?,?,? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? 3
BASIC GRAPH 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). deg(?) = 2 deg(?) = 4 deg(?)= 4 deg(?) = 1 deg(?) = 3 deg(?) = 4 deg(g)= 0 4
BASIC GRAPH TERMINOLOGY Isolated: A vertex of degree zero is called isolated. It follows that an isolated vertex is not adjacent to any vertex. Vertex g is isolated. deg(?) = 2 deg(?) = 4 deg(?)= 4 deg(?) = 1 deg(?) = 3 deg(?) = 4 deg(g)= 0 5
BASIC GRAPH TERMINOLOGY Pendant: Avertex is pendant if and only if it has degree one. Vertex ? is pendant. deg(?) = 2 deg(?) = 4 deg(?)= 4 deg(?) = 1 deg(?) = 3 deg(?) = 4 deg(g)= 0 6
BASIC GRAPH TERMINOLOGY Example 1: What are the degrees and what are the neighborhoods of the vertices in the following graph? deg(?) = deg(?) = deg(?) = deg(?) = deg(?) = 7
BASIC GRAPH TERMINOLOGY Example 1: What are the degrees and what are the neighborhoods of the vertices in the following graph? deg(?) = 4 deg(?) = 6 deg(?)= 1 deg(?) = 5 deg(?) = 6 8
BASIC GRAPH TERMINOLOGY Example 1: What are the degrees and what are the neighborhoods of the vertices in the following graph? deg(?) = 4 deg(?) = 6 deg(?)= 1 deg(?) = 5 deg(?) = 6 Vertex ? is pendant 9
BASIC GRAPH TERMINOLOGY Example 1: What are the degrees and what are the neighborhoods of the vertices in the following graph? ?(?) = ?(?) = ?(?) = ?(?) = ?(?) = 10
BASIC GRAPH TERMINOLOGY Example 1: What are the degrees and what are the neighborhoods of the vertices in the following graph? ?(?) = {?,?,?} ?(?) = {?,?,?,?,?} ?(?) = ? ?(?) = {?,?,?} ?(?) = ?,?,? 11
BASIC GRAPH TERMINOLOGY Example 2: What are the degrees and what are the neighborhoods of the vertices in the following graph? Number of vertices = 5 Number of edges = 13 12
BASIC GRAPH TERMINOLOGY Example 2: What are the degrees and what are the neighborhoods of the vertices in the following graph? deg(?) = deg(?) = deg(?) = deg(?) = deg(?) = 13
BASIC GRAPH TERMINOLOGY Example 2: What are the degrees and what are the neighborhoods of the vertices in the following graph? deg(?) = 6 deg(?) = 6 deg(?)= 6 deg(?) = 5 deg(?) = 3 14
BASIC GRAPH TERMINOLOGY Example 2: What are the degrees and what are the neighborhoods of the vertices in the following graph? ?(?) = ?(?) = ?(?) = ?(?) = ?(?) = 15
BASIC GRAPH TERMINOLOGY Example 2: What are the degrees and what are the neighborhoods of the vertices in the following graph? ?(?) = {?,?,?} ?(?) = {?,?,?,?} ?(?) = ?,?,? ?(?) = {?,?,?} ?(?) = ?,?,? 16
BASIC GRAPH TERMINOLOGY The Handshaking Theorem: Let ? = (?, ?) be undirected graph with E edges. Then 2 E = deg(?) ? ? edge Edge having two endpoints and a handshakeinvolving two hands. 17
BASIC GRAPH TERMINOLOGY Example 3: How many edges are there in an undirected graph with 10 vertices each of degree six? 18
BASIC GRAPH TERMINOLOGY Example 3:Answer How many edges are there in a graph with 10 vertices each of degree six? 2 E = deg(?) ? ? Solution: Because the sum of the degrees of the vertices is 6 10 = 60, it follows that 2E = 60. Therefore, E = 30. 19
BASIC GRAPH TERMINOLOGY Definition 4: 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). The initial vertex and terminal vertex of a loop are the same. edge (u, v) ? ? 20
BASIC GRAPH TERMINOLOGY Definition 5: In a graph with directed edges the in-degree of a vertex ?, denoted by deg (?), is the number of edges with ? as their terminal vertex. The out-degree of ?, denoted by deg+(?), is the number of edges with ? as their initial vertex. (Note that a loop at a vertex contributes 1 to both the in- degree and the out-degree of this vertex.) 21
BASIC GRAPH TERMINOLOGY Example 4: Number of vertices = Number of edges = deg (?) = deg (?) = deg (?) = deg (?) = deg (?) = deg (?) = deg+(?) = deg+(?) = deg+(?) = deg+(?) = deg+(?) = deg+(?) = 22
BASIC GRAPH TERMINOLOGY Example 4: Number of vertices = 6 Number of edges = 12 deg (?) = 2 deg (?) = 2 deg (?) = 3 deg (?) = 2 deg (?) = 3 deg (?) = 0 deg+(?) = 4 deg+(?) = 1 deg+(?) = 2 deg+(?) = 2 deg+(?) = 3 deg+(?) = 0 23
BASIC GRAPH TERMINOLOGY Theorem3: 24
BASIC GRAPH TERMINOLOGY Example 4: Recall: Number of vertices = 6 Number of edges = 12 deg (?) = 2 deg (?) = 2 deg (?) = 3 deg (?) = 2 deg (?) = 3 deg (?) = 0 deg+(?) = deg+(?) = deg+(?) = deg+(?) = deg+(?) = deg+(?) = 4 1 2 2 3 0 25
