This article is about Graph Theory that describes concepts related to graphs such as a graph, vertex, edge, Euler graph, self-loop, etc. with proof and example.
Graph Theory: Graph Theory deals with the study of graphs that concerns the relationship among vertices and edges. It is used to facilitate the study of algorithms like Kruskal’s algorithm, Prim’s algorithm, Dijkstra’s algorithm etc. There is a main relationship between topology and graph theory, it is applied in the different types of topologies like star, bridge, series, parallel and network topologies etc.
Graph: A graph is the collection of vertices and edges denoted as G(V,E), where V={v1 , v2, v3,…., vn} are called vertices and E={e1, e2, e3,….,en } are called edges . The vertex v1 is called the initial vertex and the vertex vn is called the terminal vertex. Each edge is associated with an unordered pair of vertices.
Simple Graph: A graph having no self loop and parallel edges.
Parallel Edges: Any two edges having the same starting and ending vertices.
In above graphs, V = {v1, v2} and E = {e1, e2}. Since edge number 1 and 2 are having the same starting and ending vertex, therefore e1 and e2 are parallel edges.
Self loop: An edge having the same starting and ending vertex.
In above graph, edge number 5 i.e., e5 having the same starting and ending vertex, therefore it is self loop.
Finite Graph: A graph having a finite number of vertices is called a finite graph.
Infinite Graph: A graph having an infinite number of vertices is called an infinite graph.
Degree of vertex: The number of edges connecting to a vertex.
Degrees of vertex:
d(v1) = 1
d(v2) = 3
d(v3) = 3
d(v4) = 2
d(v5) = 1
Handshaking Lemma: A graph G is said to be Handshaking Lemma, if the graph has the sum of degree of vertices is twice the number of edges.
Formula:
Fig. 1
Proof: Consider the Fig.1. The number of vertices is 5 and edges are 5.
Sum of degrees of vertex = d(v1) + d(v2) + d(v3) + d(v4) + d(v5)
1 + 3 + 3 + 2 + 1 = 10
Sum of degrees of vertex = 2e
10 = 5
Therefore,
Pendent vertex: A vertex with degree one is called Pendent vertex.
Isolated vertex: A vertex with degree zero is called isolated vertex.
Null graph: A graph without any edge is called null graph.
Theorem: Prove that the number of vertices of odd degree in a graph is always even.
Consider a graph with “n” vertices and “e” edges.
Now, break vertices into two parts:
- odd degree of vertices.
- even degree of vertices.
Let “k” be the odd degree vertices and “J” be the even degree vertices.
We know it by Handshaking Lemma that the sum of number of all the edges is twice the sum of the degree of all the vertices.
Therefore, the equation number (2) is an even number.
Each d(vj)is even (since the sum of an even numbers is an even number). Therefore equation number (2) is an even number.
The total number of terms in the sum must be even. Hence the number of vertices of odd degree in a graph is always even.
Walk: In a graph, a walk is a sequence of vertices and edges are connected, that can end at the same or different vertex.
Note: Vertices and Edges are allowed to repeat.
Open Walk – If starting and ending vertices are different.
Pattern: 1>2>3>1>4>3
Closed Walk – If the starting and ending vertices are same.
Pattern: 1>2>3>4>5>1
Pattern: 1>2>3>1
Trail – Trail is an open walk in which no edge is repeated.
Note: Vertex can be repeated.
Fig. 1
Fig. 2
Path – It is sequence of edges which connects with sequence vertices and all vertices are different. In other words, if in a walk there is no vertex and edge is repeated then it is Path.
Note: Neither vertices nor edges are allowed to repeat.
Important Points
1. A path is also called simple path or an elementary path
2. A path does not intersect itself.
3. A self loop can be include in a walk but not in a path.
4. The number of edges in a path is called length of the path
Cycle – A graph G is said to be Cycle, if it is as same as Path but the additional condition is Path must be closed.
Note: Neither Vertex nor Edge is allowed to repeat.
Note: Starting and ending vertex must be same.
Circuit – A graph G is said to be Circuit, if it is as same as Trail but the Trail must be closed. In other words, A graph with no edge is repeated but only vertex can be repeated, and it is closed also.
Note: Edge not allowed to repeat.
Note: Only Vertex can be repeated.
Connected graph: A graph G is said to be Connected graph, if any two vertices are connected in the graph. In other words, there is a path between every pair of vertices and should be some path traverse. Otherwise, it is said to be disconnected.
Fig. 1
Fig. 2
In above graph, Fig.1 represents the graph is connected.
In above graph, Fig.2 represents the graph is disconnected because there is no path from V2 to V4.
Directed graph: A graph is said to be a directed graph if edges are connected with vertices and edges have direction with them.
Undirected graph: A graph is said to be a directed graph if edges are connected with vertices and edges does not have direction with them.
Subgraph – A graph ‘g’ is said to be a subgraph of a graph ‘G’, if all the vertices and all the edges of ‘g’ are in ‘G’ and each edge of ‘g’ has the same end vertices in ‘g’ as in ‘G’.
In other words, a subgraph is a extracted part of main graph. If all the vertices and edges of subgraphs belongs to main graph.
Fig.1 – Original Graph
Fig.2 – Sub-graph
In the above Fig. 1 is a graph and Fig. 2 is a subgraph of a graph Fig. 1 where Fig. 2 contains all the edges in the graph Fig. 1.
Note: Points to be remembered
1.Every graph has its own subgraph
2.A subgraph of a graph Fig. 1 is a subgraph of Fig. 1
3.A single vertex in a graph Fig. 2 is also a subgraph of Fig. 1
4.A single edge in Fig. 2 together which its end vertices is also a subgraph of Fig. 1
Edge disjoint – If two or more subgraphs ‘g1’ and ‘g2’ of G are said to be edge disjoint of ‘G’, if both ‘g1’ and ‘g2’ do not have any edges in common.
Fig. ‘G’
Fig. ‘g1’
Fig. ‘g2’
The above figure represents the edge disjoint sub-graphs.
Note: Edge disjoint graphs do not have any edge in common, but they may have vertices in common.
Vertex disjoint – Subgraphs that do not have vertices in common said to be vertex disjoint subgraphs.
Fig. 1 – Original Graph
Fig. 2 – Subgraph
Fig. 3 – Subgraph
The above figures represents the vertex disjoint subgraphs where Fig.1 and Fig.2 do not have any vertices in common.
Euler Graph – A graph is an Euler graph if a closed walk contains all the edges of the graph.
Fig. 1
Fig. 2
Fig. 3
Isomorphic – Two graphs G and G’ are said to be isomorphic to each other if there is one to one connection between vertices and their edges such that an incidence relationship is established.
In other language, having two different graphs with the same number of vertices and edges.
Note: In both graph, degree of vertex of each vertex should be same.
Fig. 1
Fig. 2
In the above graph Fig.1 the vertices v1,v2, and v3 correspond to Fig.2 the v1,v2, and v3 respectively. The edges in Fig.1, 1,2, and 3 correspond to Fig.2, 1,2, and 3 respectively . Therefore G And G’ are isomorphism.
Reachability – It is a connection between two vertices. Vertex “A” is to be reachable from vertex “B” provided that there is a path from “A” to “B”.
Fig. 1
If you find anything incorrect in the above-discussed topic and have further questions, please comment below.
Connect on:
