Graph Theory

A graph X ( A, B), includes two sets A and B. The elements of A are the vertices of graph X whereas the elements of B are the edges of graph X. Each edge is defined as the pair of vertices. For example, the set A {1, 2, 3, 4, 5}, and set B {1, 2}, {2, 3}, {3, 4}, {4, 5} defines a graph with 5 vertices and 4 edges respectively.

Graphs have a natural linear representation in which each vertex is represented by a point and each edge by a line joining two points.

To have a better understanding of graphs, we should understand its base - Graph Theory. In this article of graph theory notes, we will discuss what is graph theory, and history of graph theory in detail. We will also discuss graph theory questions, terminologies of graph theory, and the difference between circuit and cycle in graph theory.

What is Graph Theory?

In Mathematics, graph theory is the study of mathematical objects known as graphs, which include vertices (or nodes) joined by edges (vertices in the figure below are numbered circles and the edges join the vertices).

A situation in which one wishes to observe the structure of a fixed object is potentially a problem for graph theory. Examples of graph theory cannot only be seen in Mathematics but also in Computer Science and Physics.

History of Graph Theory

The basic idea of a graph was first introduced by Swiss mathematician Leonhard Euler in the 18th century. His attempt and utmost solutions to the famous Konigsberg bridge issues introduced the concept of graph theory.

The German city of Konigsberg is located on the Pregolya river. The graphical layout consists of four main bodies of land joined by a total of seven bridges. The question raised to Euler was direct: Was it possible to go for a walk through the town in such a manner as to cross over each bridge only once (also known as an Euler walk)?.

Euler observed the four bodies of land and the seven bridges. This helped him to draw out the first known visual representation of a modern graph. A modern graph (that can be seen in the above image B) is represented by a set of points, known as vertices or nodes are joined by a set of connecting lines known as edges.

Euler first made an attempt to construct the path of the graph. Later, while experimenting with different theoretical graphs with alternative numbers of vertices and edges, he predicted a general rule.

He concluded that in order to be able to walk in the Euler path, a graph should have none or two odd numbers of nodes. From there, the concept of graph theory was introduced.

Terminologies of Graph Theory

A non-trivial graph includes one or more vertices (or nodes), joined by edges. Each edge exactly joins two vertices. The degree of a vertex is defined as the number of edges joined to that vertex. In the graph below, you will find the degree of vertex A is 3, the degree of vertex B and C is 2, the degree of vertex D is 3, and the degree of vertex E is 0.

Note: If the degree of each vertex is similar for a graph, then we can consider it as the degree of the graph.

A graph is said to be a connected graph if there exists a possibility to reach any vertex by crossing the edges from one vertex to another. The graph given above is not connected, although it includes a path between any two of the vertices A, B, C, D and E.

A graph is said to be a complete graph if it includes an edge joining every two pairs of vertices. The graph given above is not complete but can be completed by including extra edges as shown below:

Difference Between Circuit and Cycle in Graph Theory

A cycle in graph theory is a closed path i.e., we start and end at the same vertex. In between, we don't get any chance to travel twice.

It is helpful to define trails before moving on to circuits. Trails are defined as walks where no edge is repeated.

The circuit is defined as a closed trail. It means that it is a path that starts and ends at the same vertex.

Graph Theory and Application Question Bank

If you are looking to brush up on the concepts of graph theory, then you should try to solve the different types of graph theory questions given in Graph theory and application question bank. Solving the graph theory questions will help you to understand the concept of graph theory in a better way.  Few graph theory questions are as follows:

1. Define the Following Terms

• Graph theory

• Simple Graph

• Complete Graph

• Null Graph

• Subgraph

• Euler's Graph

• Incident, adjacent, and degree

• Cycles in graph theory

2. Mention the few problems solved by the application of graph theory.

3. Write different applications of graphs.

4. State that a simple graph with n vertices and k components can have utmost (k- 1) edges.

5. The stage that connected graph G is an Euler graph if all the vertices are given in even degree.

6. What is a  Chromatic number?

7. Explain different types of graphs.

8. What is an algorithm in graph theory?

9. What are the different types of directed graph?

10. What is the circuit, path, and walk?

Solved Examples

1. Find the chromatic number of the complete graph Kₙ given below.

Solution:

In a complete graph Kₙ, each vertex is adjacent to its remaining (n -1) vertex. Hence, a new colour is required for each vertex. Therefore, the chromatic number of complete graph Kₙ = n. 

2. Find the matching number of the graph given below.

Solution:

There are a total of 9 vertices and we can match only 8 vertices as shown below. Hence, the matching number of graphs given is 4.