* Graph:* A graph is said to be planner if it can be drawn on a plane in such a way that no edges cross one another except of course at common vertices.

**Finite region and infinite region**: A region is said to be finite if it is area is finite and infinite if its area is infinite.

**Degree of regions:** The number of edges on the boundary of a region is degree of regions.

When an edge occurs on the boundary it contributes two to the degree.

∴ Sum of degree of region =2.e

Note that: In a simple graph (not contain a loop) there is at least three edges or vertices for a finite region.

* Directed graph:* A directed

*graph*or digraph is defined abstractly as an ordered pair (V.E) where (1) the elements of the set V are called vertices or nodes or point.

(2) The elements of the set E are ordered pair (u,v) of vertices called arc’s or directed edge or simply edge.

**Isolated vertex or point**: A vertex is said to be isolated vertex or point if there is no edge with it.

**Degree of vertex:** The degree of a vertex in a graph G, written deg(v) is equal to the number of edge in G which contain v.

**Isomorphism:** Let G_{1}=G_{1}(V_{1}, E_{1}) and G_{2}=G_{2}(V_{2}, E_{2}) be two graph, then G_{1} is said to be isomorphic to G_{2} if there is a one to one function φ from V_{1} to V_{2} such that

(i) If uv is an edge in E_{1} , then φ(u) φ(v) is an edge in E_{2}.

(ii) Every edge in E_{2} has the form φ′(u) φ′(v) for some edge uv∈E_{1}.

G_{1} is isomorphism to G_{2} then G_{1}≅G_{2}.

If G_{1} and G_{2} isomorphic graph then G_{1} and G_{2} have the

(i) Same number of edge.

(ii) Same number of vertices.

(iii) Same degree sequence.

**Sub-graph:** Let G =(V, E) be a graph. A graph G′ = (V′, E′) is said to be a sub-graph of G if E′ is a subset of E and V′ is a subset of V such that the edges in E′ are incident only with the vertices in V′.

Example:

**Spanning sub-graph:** A sub-graph G′ of a graph G is said to be spanning sub-graph if it contains all the vertices of G.

**Complement of sub-graph:** The complement of a sub-graph G′ = (V′, E′) with respect to the graph G is another sub-graph G″ = (V″, E″) such that

E″ is equal to E- E′ and V″ contains only the vertices with which the edges in E″ are incident. For example Fg-2 shows the complement of the sub-graph in Fig-1.

**Complete Graph:** The simple graph that contains exactly one edge between each pair of distinct vertices is called a called complete graph. It is denoted by K_{n} where, n is the number of vertices.

**Regular graph:** A graph G is regular of degree K or K-regular if every vertex has degree K. In other words a graph is regular if vertex has the same degree.

**Path:** A path is a sequence of edges that begins at a vertex of a graph and travel along edges of the graph always connecting pairs of adjacent vertices.

**Circuit or Cycle:** A path of length n≥1 that begins and ends at the same vertex is called a circuit or cycle.

**Simple path:** A path or circuit is simple if does not contain the same edge more than once.

**Elementary path:** A path is elementary if it does not contain the same vertex more than once.

**Elementary path:**A path is elementary if it does not contain the same vertex more than once.

**Walk:** A walk in a graph is an alternating sequence of vertices and edges beginning and ending with a vertex in which vertex is incident with the edge which follows and the last vertex is incident with the edge which precedes it.

**Trail:** A walk in which all edges are distinct is called a trail.

Example: