The two different structures of discrete mathematics are graphs and trees. The set of lines interconnect the set of points in a graph. The set of points are called as nodes and the set of lines as edges. In the areas of mathematics, engineering and computer science, the study of graph is very important. The study of graph is also known as Graph theory.
A graph (denoted as G=(V,E)) consists of a nonempty set of vertices or nodes V and a set of edges E.
Example – For instance, a graph is considered as G=(V,E)) where V={a,b,c,d}and E={{a,b},{a,c},{b,c},{c,d}}
Degree of a Vertex – The number of edges that are incident with the vertex V is termed as the degree of a vertex V of the graph G, denoted by deg (V).
Vertex

Degree

Even / Odd

a

2

even

b

2

even

c

3

odd

d

1

odd

Even and Odd Vertex – The vertex is even when the degree of vertex is even and the vertex is odd when the degree of vertex is odd.
Degree of a Vertex – The largest vertex degree of that particular graph is considered as the degree of the graph.
The Handshaking Lemma – The sum of all the degrees of the vertices is equal to double the number of edges.
The following are the different types of graphs available:
A graph with no edges is known as a null graph. The null graph of n vertices is denoted by
When the graph is undirected without any loops or multiple edges, such a graph is known as Simple/strict graph.
When between the same set of vertices, multiple edges are allowed, it is known as a Multigraph. Multigraph have at least one loop or multiple edges.
When the ordered vertex pair make up the edge set, then the graph G=(V,E) is known as a directed graph and when the unordered vertex pair make up the edge set, then the graph is known as a undirected graph.
If any two vertices of a graph are connected by a path, the graph is said to be connected. If at least two vertices of the graph are not connected by a path, the graph is said to be disconnected. If a graph G is disconnected, then every maximal connected subgraph of G is called a connected component of the graph G.
When all the vertices of the graph have same degree, the graph is said to be a regular graph. In a graph G of degree r, the degree of each of the vertex of G is r.
When exactly one edge joins every two vertices pair, the graph is said to be a complete graph. The complete graph with n vertices is denoted by
The graph with a single cycle is known as a cycle graph. The cycle graph with n vertices is represented by
When graph G is split into two disjoint sets, V1 and V2, such that each of the vertex in V1 is joined to each of the vertex in V2 by each of the edge of the graph. And no edges in G should connect either two vertices in V1 or two vertices in V2 and such a graph is known as bipartite graph.
In a bipartite graph, each vertex of the first set is joined to every single vertex in the second set, such a graph is known as complete Bipartite Graph and is denoted by
A graph can be represented in two ways:
A 2d array of size V×V where V is the number of vertices in a undirected graph, is known as an adjacency Matrix A[V][V] .
If there is an edge between
Then the value of
Otherwise the value is 0.
For a directed graph,
If there is an edge between
Then the value of
Otherwise the value is 0.
For instance, consider the following undirected graph and construct the adjacency matrix 
For the above undirected graph, the adjacency matrix is as follows:
a

b

c

d


a

0

1

1

0

b

1

0

1

0

c

1

1

0

1

d

0

0

1

0

For instance, consider the following directed graph and construct the adjacency matrix 
For the above undirected graph, the adjacency matrix is as follows:
a

b

c

d


a

0

1

1

0

b

0

0

1

0

c

0

0

0

1

d

0

0

0

0

A graph G with V number of vertices is represented by an array (A[V]) of the linked list in adjacency list.
The linked list of the vertices adjacent to the Vx−th vertex is represented by the entry
For an undirected graph, the adjacency list is depicted below:
Planar graph – Without crossing the edges when a graph can be drawn plane, the graph is called as a planar graph. It is known as embedding the graph in the plane.
Nonplanar graph – When it is not possible to draw a graph in a plane without crossing edges, it is nonplanar graph.
When the same numbers of vertices are connected in the same way in two different graphs G and H, then they are called as isomorphic graphs, represented as G≅H.
The graphs are said to be nonisomorphism when any one of the following conditions appears:
Example
The examples for isomorphic graphs is depicted below:
The mapping between the graphs G and H in such a way that h:G→H, such that (x,y)∈E(G)→(h(x),h(y))∈E(H). The adjacent vertices of graph G are mapped to the adjacent vertices of graph H.
If a graph has a closed trail including every edge of the graph G, such a connected graph is known as Euler graph. The path that is used by every edge only once is the Euler path which starts and ends at different vertices.
The circuit that uses every edge of the graph only once is known as Euler circuit. Euler circuit starts and ends at the same vertex. An Euler graph is a connected graph when all the vertices of G are of even degree.
The above graph is an Euler graph as “a1b2c3d4e5c6f7g” covers all the edges of the graph.
If there is a cycle in the connected graph that includes every vertex of G is known as Hamiltonian cycle. The walk that passes through each vertex exactly once in a graph G is known as Hamiltonian walk.
If G is a simple graph with n vertices, where
for each vertex v, then the graph G is Hamiltonian graph. This is called Dirac's Theorem.
If G is a simple graph with n vertices, where
for each pair of nonadjacent vertices x and y, then the graph GG is Hamiltonian graph. This is called Ore's theorem.


Discrete Mathematics Related Tutorials 


Statistics Tutorial 
Discrete Mathematics Related Interview Questions 


Statistics Interview Questions  Physics Interview Questions 
Chemistry Interview Questions  Teacher Interview Questions 
Mathematics Interview Questions  Physical Design Engineer Interview Questions 
Geometric Dimensioning and Tolerancing (GD&T) Interview Questions 
Discrete Mathematics Related Practice Tests 


Statistics Practice Tests  Physics Practice Tests 
Chemistry Practice Tests 
Discrete Mathematics Tutorial
Discrete Mathematics
All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.