Some Important Definition of Graph Theory

1. Self –Loop:- An edge whose end vertices are same is called a self-loop.

2. Simple Graph:- A graph having no parallel edges and no self loops is called simple graph.

3. Incidence:- When a vertex is an end vertex of an edge then the vertex & the edge are called incident to each other.

4. Degree of vertex:- The number of edges incident to a vertex, with self loop counted twice, is called degree of the vertex.

  

5. Regular graph:- A graph in which all vertices are of equal degree is called a regular graph

6. Isolated Vertex:- There may exist some vertex which are not connected by lines. A vertex having no incident edge is called an isolated vertex. (The degree of an isolated vertex is 0)

7. Pendant Vertex:- A vertex whose degree is 1.

8. Complete graph:- A simple graph is called a complete graph if each pair of distinct vertices is joined by an edge.(A complete graph is always a regular graph)

9. Spanning Sub graph:-A subgraph G₁ of a graph G is called a spanning sub graph of G if G and G₁ have same vertex set.

10. Walk(or Chain):-A finite alternating sequence of vertices and edges, beginning and ending with vertices, such that each edge is incident to its preceding & following vertices is called walk.

Note-   

i)  The origin & terminates of a walk may be same.

ii) A vertex may appear twice or more in a walk.

iii)                 An edge may appear twice or more in a walk.

iv)                 A self – loop can be included in a walk.

           

11. Length of walk:- The number of edges in a walk is called the length of the walk.

12. Closed & open walk:- If a walk begins & ends at the same vertex then the walk is called closed walk. A walk that is not closed is called open walk.

13. Circuit (or Cycle):- A closed walk in which no vertex appear twice or more is called a circuit.

Note-

i)  A circuit is a non – intersecting walk.

ii) A circuit is a sub graph in which every vertex is of degree 2.

iii)                 Every self – loop is a circuit but converse is not true.

14. Path (or Simple path):- An open walk in which no vertex appears twice or more is called a path.

15. Connected or Disconnected graph:- A graph is called connected if there exist at least one path between every pair of vertices in the graph.

             A graph is called disconnected if there exist at least two vertices having no path between them.