Department of Mathematics Elementary Graph Theory Lecture 2
Ex: Determine the number of edges in a graph of order 6 in which 2 of the
vertices of degree 4 and 4 of the vertices of degree 2, and construct them.
Solution: Assume that such a graph of order 6 has q edges. then by
Handshaking Theorem
degG (v) 2q
vG
6
degG (vi ) 2q
i 1
Without losing the generality assume the first two vertices has degree 4 and the
last vertices has degree 2, then we get
2 6
4 2 2q
i 1 i 3
2(4) 4(2) 2q
16 2q
q 8
K 2,4
Some Types of Graphs
1. Complete graph
A simple graph G is said to be complete if every vertex in G is connected with
every other vertex ( if G contains exactly one edge between each pair of distinct
vertices), it is denoted by K n .
n(n 1)
K n has exactly 2
edges
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 2
The graphs K n for n = 1, 2, 3, 4, 5, 6 are show in the next Figure .
2. Bipartite graph
A graph G is said to be bipartite graph if the vertex set can be partitioned
into two sets, such that each edge in G joins the vertex of the first set with the
vertex of the second set.
A graph G is said to be n-partite graph if the vertex set of G can be
partitioned into n sets V1 , V2 , , Vn , such that each edge in G joins the vertex of
the set Vi with the vertex of the set Vj , i j, i, j 1, 2, ,n .
3. Complete bipartite graph
A graph G is said to be complete bipartite graph if its vertices can be
partitioned into two sets V1 and V2 , such that each vertex of the set V1 adjacent
with all vertices of the set V2 . If the sets have m and n vertices, then the
complete bipartite graph denoted by K m, n .
p(K m, n ) m n and q(K m, n ) mn
Dr. Didar A. Ali 2
Ex: Determine the number of edges in a graph of order 6 in which 2 of the
vertices of degree 4 and 4 of the vertices of degree 2, and construct them.
Solution: Assume that such a graph of order 6 has q edges. then by
Handshaking Theorem
degG (v) 2q
vG
6
degG (vi ) 2q
i 1
Without losing the generality assume the first two vertices has degree 4 and the
last vertices has degree 2, then we get
2 6
4 2 2q
i 1 i 3
2(4) 4(2) 2q
16 2q
q 8
K 2,4
Some Types of Graphs
1. Complete graph
A simple graph G is said to be complete if every vertex in G is connected with
every other vertex ( if G contains exactly one edge between each pair of distinct
vertices), it is denoted by K n .
n(n 1)
K n has exactly 2
edges
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 2
The graphs K n for n = 1, 2, 3, 4, 5, 6 are show in the next Figure .
2. Bipartite graph
A graph G is said to be bipartite graph if the vertex set can be partitioned
into two sets, such that each edge in G joins the vertex of the first set with the
vertex of the second set.
A graph G is said to be n-partite graph if the vertex set of G can be
partitioned into n sets V1 , V2 , , Vn , such that each edge in G joins the vertex of
the set Vi with the vertex of the set Vj , i j, i, j 1, 2, ,n .
3. Complete bipartite graph
A graph G is said to be complete bipartite graph if its vertices can be
partitioned into two sets V1 and V2 , such that each vertex of the set V1 adjacent
with all vertices of the set V2 . If the sets have m and n vertices, then the
complete bipartite graph denoted by K m, n .
p(K m, n ) m n and q(K m, n ) mn
Dr. Didar A. Ali 2
