Discrete mathematics is a distinct mathematical term rather than being continuous term. Graph, integers, etc. are the part of discrete mathematics it excludes the topics such as of Calculus and analysis, etc. or in short we can say discrete mathematics deals with the countable Sets. As such there is no specified definition of discrete mathematics. |

**A graph consists of nodes and edges, these edges are incident to a node and these nodes are also called as vertices of graph.**

Also graphs are ubiquitous models which may be useful for various Relations.

Graphs has wide use due to their practical importance. They can be implemented practically.

Wide use of graph is its use in to find out the shortest path and minimum cost in various transportation problems.

**A graph can be referred to collection of vertices and edges. These vertices are also known as nodes, edges are basically used to connect nodes.**

Nodes or vertices are indicated by Circle or dot and line between various nodes represent edges.

Edges can be undirected which are also known as asymmetric or undirected also called symmetric. These edges may be weighted or unweighted. Weighted edge refers that some distance exists between two nodes and unweighted edge means that there is no distance between two vertices.

Application of graph theory shortest path is the shortest path problem which targets to minimize the sum of weights of its edges which connects two or more vertices.

Graphs may be undirected in which the shortest path problem may be explained with following description:

Lets consider a weighted graph in which a Set 'X' of vertices, a set 'Y' of edges and f : E → R which is showing a weight function , and elements 'a' and 'b' of 'X', find a path 'Z', an order of edges from a to b of X so that

∑ f(z),

Where z ε Z,

Shows minimal path which is connecting a to b.

Shortest path problem may also be called as single - pair shortest path problem to differ it from single - source shortest path problem, single - destination shortest path problem, all-pairs shortest path problem.

**Path can be defined as distance traveled by an object from one Point to another. Points are called vertices of the path.**Let there be two vertices A and B, then path between these two vertices is called A – B path. The distance between these two points or vertices is known as edge. Hence a path may include several vertices and edges. The Set of vertices and edges actually forms a graph which is called path graph. A path graph can also be defined as set of nodes (vertices) and set of lines that connect these nodes.

Open path is a path in which first and last vertices are not connected. If first and last vertices are same, then this type of path will be called as cycle graph. If vertices are connected to each other by various edges in a sequence then this sequence of vertices in a graph is called as paths in graph theory.

Figure shown above has five vertices (nodes) and five edges (lines) to connect the vertices. Here first and last vertices that is vertex number 1 and 5 are distinct that’s why this type of graph is called as path graph. There is no meaning of length of lines in graph theory since lines are only used to show relationship between vertices. In above figure, node 1 is connected to node 2 and node 3. Edge is used to define this relationship. Various types of path graphs are directed graph, valued graph etc.

**Cycle graph can be defined as a graph which is comprised of single cycle. In other words, if vertices in given graph are connected in a closed form then graph is called as cycle graph.**A cycle graph may can also be referred to circular graph. In a cycle graph, if there are 'n' vertices then cycle graph will be denoted by C n and number of vertices (nodes) in C n is equals to the number of edges and degree of each vertex is 2 that is each vertex has exactly two edges which are incident to node (vertex). A cycle graph has common first and last vertex. This can be shown by the following figure.

In above figure, it is clear that first and last Point is ‘a’ that’s why this is called as cycle graph. Hence it can be said that cycle is a closed graph. If there are four vertices in the graph then it is called as 4 – cycle.

Cycle in graph theory can be Odd or even cycle. These two terms can be defined as follows. If there are odd Numbers of edges in a cycle graph then it will to odd cycle graph and if number of edges (lines) is even in cycle graph then this type of graph is called even cycle graph.

Degree of cycle graph is given for vertices and can be calculated by counting the number of lines meeting on that vertex.

Lets consider an example as shown below:

The degree of node ‘A’ in the above graph is three since there are three edges incident on it. Similarly the degree of B, C and D will be given as deg (B) = 2, deg (C) = 4 and deg (D) = 1.

Connectivity is related to the network flow problems. It is used to find out the minimum number of vertices or edges which can be used to disconnect the remaining nodes from each other. Connectivity of a graph actually shows the robustness of the graph. If there are two nodes or vertices A and B, then they will be said connected if there is a path from A to B. Otherwise, they are disconnected.

Menger's theorem is one of the important theorems which is used to define the concept of connectivity in graphs. This theorem, actually describes the line (edge) connectivity of a graph in terms of the number of independent paths between vertices (nodes). Let’s try to understand the Menger's theorem. If A and B are the two vertices of a graph, then collection of paths between A and B is said free if none of the two vertices A and B share a vertex and if no two paths share an edge, then it is called as edge – dependent.

Let’s consider that maximum number of free paths between A and B is C′ (A, B) and highest number of edge free paths between A and B is written as D′ (A, B) then according to Menger's theorem, the local connectivity equals C′ (A, B) and local edge-connectivity equals D′ (A, B) for every pair of vertices A and B.

Let’s see Connectivity In Graph Theory.

If we denote the edge-connectivity by E then it will be defined as minimum number of edges which on removing, disconnects the graph. When E ≥ m, graph is called m-edge-connected graph. If we write Connectivity of Complete Graph by m (mk), then connectivity of complete graph m k is m – 1. Vertex Connectivity can be defined as smallest number of vertices, which when removed leaves the graph disconnected.