Graph Theory

A graph is a drawing or a diagram consisting of a collection of vertices together with edges joining certain pairs of these vertices. Mathematically, we can write a graph as:

G = [V(G), E(G)]

where V(G) = Vertex set of graph G
E(G) = Edge set of graph G

Some definitions:

Parellel Edges: If two (or more) edges of a graph G have the same end vertices then these edges are called Parellel.

Isolated Vertex: A vertex of graph G, which is not the end of any edge is called Isolated.

Neighbours or adjacent Vertex: Two vertices which are joined by an edge are called adjacent or neighbours. The set of all neighbours of vertex v is called Neighbourhood set of v and is denoted by N(v).

Incidence: An edge e of grapg G is said to be incident with the vertex v if v is an end vertex of e (or v is incident with e). Two edges e and f which are incident with common vertex v are said to be adjacent. An edge could be incident with either 1 or 2 vertices (1, in case of loop), whereas a vertex could be incident on any finite number of edges.