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 G1=G1(V1, E1) and G2=G2(V2, E2) be two graph, then G1 is said to be isomorphic to G2 if there is a one to one function φ from V1 to V2 such that
(i) If uv is an edge in E1 , then φ(u) φ(v) is an edge in E2.
(ii) Every edge in E2 has the form φ′(u) φ′(v) for some edge uv∈E1.
G1 is isomorphism to G2 then G1≅G2.
If G1 and G2 isomorphic graph then G1 and G2 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′.
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 Kn 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.
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.