Lecture notes
Some Type of Graph & Graph representations & Properties of adjacency matrix
- Module
- Abacus College,Oxford (12)
Lecture notes of 6 pages for the course Abacus College,Oxford at BITE (Beast Curse for you)
[Show more]
Seller
Follow
Content preview
Department of Mathematics Elementary Graph Theory Lecture 2Ex: 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller bilal-guma. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £2.45. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
52928 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now