5.
Groph Theory
5.1. Introduction to raph
A1 Defini thon Asiple reph G V, Ef consist of V,a
non-empty
emply se ver tices and E, a set onordered paiS
dislinch elements of- v caled edges.
Ler
V a, b, c, d f
E (a,b),(a, c), (b, e), (c,d)
So, he raph ilf
a)
No loop
No mu hiple edges
No diractiom
Muti-avaph
bet" tuo nodes
Mu hiple edges
No loo
No cie chon
Psevdogreph/Unciecfed groph
- Auy Ithpe. odas
-Loop is alloded
No oirechon
Thocled raph
Direcked oces
Loop alloaded
d Mu Hple edges
B) Basic Teri nology
Adhaceuh vertex or neiqhbovs
TOOverthces &v aye Called neighbors ar
Adhacon i they ConnecAed thve ugh an
edge
NEIGHBOR. (a) = } b,c?
NEIGHBOR(4)= {b?
Degree averlex
nomber - adges cohnecteed to a vertex.
The
e dogree oE
excep thaF a
Loof Coutrthutes tuwi cRto
loop
that vertey. That means, for a loop you have to count 2 degree
Loop
deg(a) = 2 4
) 2
deg () =
deg (c) =2
dag ( d ) 3
(o) 1
deg -
deg( ) - O
O
lsolaled verlex Verlex d1h darek.
is an isolated verlex
In G ver lex
Pendent means hanging from above
Vertex h degva 1, also called and
Pencdent verex:
In G verBex e penden vertex.
ver tex.
yee o a vertex n a diected graph
number edges eouti into the verlex,V.
Indegyee
Notahon deg (v)
In (-), Out (+) Mnemonic: MIPO (Minus In Plus Out) => Miro (Rusev)
nuuber o edges tha are
goiu ouF
Outdogre
Hhe ver ex V.
Notation dea ()
Indeqvee Out degr
le(a) = 2 deg (o) =23
degt (6) = 1
deg ( ) 2
2
deq (e)= 1 deat (e) =
de C)2 let (A) =
2
deg(c) = 1 deg (e)= O
The handshaking theorem: Imagine a social gathering where people shake hands. The degree of a person (vertex) is the number of handshakes they make. The theorem says:
The total number of handshakes made by everyone (twice what each person does) is equal to the total number of handshakes that happen (number of edges).
In other words, for an undirected graph the sum of the degrees of all vertices is always twice the number of edges.
This might seem obvious for simple graphs, but it holds true for any complex undirected graph as well.
5.2. land shaking heorem
Lo,
Let = (v,E) be an Undiveched gvaph
deg(u) = 2x1E here E|= no.et edges
LAEV
And, for direc kd qraph
do u) = Z degt(u) = E
uEV UEV
V Examples
O Ho many edqes ave there an di veched groph
wihh en vertiag oach d 62
dgres 6?
Total number d degree = Ox6 = 60
2 xE = 60 ' l E =30
Asmple araph has 24 edges and dearea
eoch ver dex is 4. Find the no o verhces .
TEl= 24
deqvec. oeaeh vorlex = 4
vl ?
Using hanclshakiu +
v] 4 = 2x IE
v= 2x 24 = 12
