Adjacent (neighbor) Vertices in Undirected Graphs
Two vertices, u and v in an undirected graph G are
called adjacent (or neighbors) in G, if {u, v} is an
edge of G.
An edge e connecting u and v is called incident with
vertices u and v, or is said to connect u and v.
The vertices u and v are called endpoints of edge
{u, v}.
Degree of a vertex
The degree of a vertex in an undirected graph is the
number of edges incident with it.
A loop at a vertex contributes twice to the degree of
that vertex.
The degree of the vertex v is denoted by deg (v)
Pendant and isolated vertices
A vertex is pendant if and only if its degree is one.
A vertex of degree zero is called isolated.
In the shown below graph , vertex (d) is pendant,
while vertex (e) is isolated
c d
b deg( d ) = 1
deg( e ) = 0
a g f e
Example
For shown below graph find:
1) The degree of each vertex.
2) The total number of degrees of all the vertices.
3) The total number of edges.
c d
b
a g f e
Solution
TOTAL NUMBER OF DEGREES OF All THE GRAPH’S VERTICES
= 2 + 6 + 4 + 1 + 0 + 3 + 4 = 20
THE TOTAL NUMBER OF EDGES
= 10
deg(c) = 4
c d
deg(b) = 6 b deg(d) = 1
deg(a) = 2 deg(e) = 0
a g f e
deg(g) = 4 deg(f) = 3
The Handshaking Theorem
“In an undirected graph, the sum of the degrees
over all the vertices equals twice the number of
edges.”
The above theorem applies even if multiple edges
and loops are present.
deg(v) 2e
vV
Example
How many edges are there in a graph with 10
vertices each of degree 5?
Solution:
Because the sum of the degrees of the vertices is
5 x 1 0 = 50,
it follows that 2e = 50.
Therefore, e = 25
Adjacent Vertices in directed graphs
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.
The in-degree and the out-degrees of
vertices in directed Graphs
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 that a loop at a vertex contributes 1 to both the
in-degree and the out-degree of this vertex.)
In a graph with directed edges:
deg
v v E
deg
vV vV
Example
For the shown graph, find
1) The in-degrees and the out-degrees
2) Total number of the in-degrees
3) Total number of the out-degrees
4) Number of the graph edges
Solution
1) The in-degrees: 2) The Out-degrees: 3) Total number of the
deg-(a) = 2 deg+(a) = 4 in-degrees = 12
deg-(b) = 2, deg+(b) = 1 4) Total number of the
deg-(c) = 3, deg+(c) = 2 out-degrees = 12
deg-(d) = 2, deg+(d) = 2 5) Number of the
deg-(e) = 3, deg+(e) = 3, graph edges =12
deg-(f) = 0 deg+(f) = 0
Special Types of Graphs
Complete Graphs (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 graphs Kn , for n = 1 , 2, 3 , 4, 5 , 6, are displayed in the
shown below figure.
Note that: Kn has n vertices and n(n - 1)/2 edges
Cycles
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 C3 , C4 , C5 , and C6 are displayed in
the Figure
Note that: Cn has n vertices and n edges
Wheels
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 by new edges.
The wheels W3 , W4 , W5 , and W6 are displayed in the
figure
Note that: Wn has n+1 vertices and 2n edges
Subgraphs
Graph G2 = (V2, E2) is a subgraph of graph
G1 = (V1, E1) if:
1) V2 V1
2) and E2 E1.
G2 G1 denotes that G2 is a subgraph of G1
Example
Is C5 a subgraph of K5 ?
K5 C5
YES
The Union of graphs
The union of two simple graphs G1 = (V1 , E1) and
G2 = ( V2 , E2 ) is the simple graph with vertex set
V = V1 V2 and edge set E = E1 E2
The union is denoted by G1 G2 .
Example (i)
Find the union of the graphs S5 and C5
Answer
The shown below graph (W5) is the union of S5
and C5
Example (ii)
Draw the graph representing the union of
G1 and G2
Answer
