Graph Theory

A graph G = (V,E) consists of two sets V and E. The elements of V are called vertices while that of E are called edges. Each edge e is associated with an unordered pair v_i,v_j of vertices

An edge having the same vertex at both ends is called a loop.

Two edges associated with the same pair of end vertices are called parallel edges.

A graph which does not contain loops or parallel edges is called a simple graph.

The number of edges incident on a vertex v with loops being counted twice is called the degree of the vertex v.

A graph in which all vertices are of equal degree is called a regular graph.

A vertex having no incident edge is called an isolated vertex.

A graph having no edges is called a null graph.

fig.1

In fig.1 , V = {A,B,C,D,E,F} are the vertices.

E = {a,b,c,d,e,f,g,h,i} are the edges.

c and f are parallel edges.

h is a loop.

The degrees of various vertices are

d(A) = 5

d(B) = 4

d(C) = 3

d(D) = 3

d(E) = 3

d(F) = 0

Theorem 1 :

The sum of the degrees of all vertices of a graph is equal to twice the number of edges of the graph.

Theorem 2 :

A graph always contains a even number of vertices of odd degree.

-----------------------------------------------------------------------------------------------------------------------------------------

233