This article is about the introduction of various graphs in Graph Theory such as Planar Graph, Subgraph, Spanning Graph, and Induced Graph with their usage and example.
Table of Contents
Graph Theory
Graph Theory is a branch of mathematics that studies graphs. Graphs are abstractions of a social network, the connections between people and events, the connections between pages on a website, or any other kind of connection.
Planar Graph
A graph is defined as a planar graph if it can be drawn in a plane and no edges intersect each other.
In other words, Planar graph edges intersect only at their endpoints. It can be drawn in such a way that no edges cross each other.
Regions of Plane
The representation of planar graphs is divided into connected parts/regions that are known as Regions of the Plane.
Degree of Region
- Degree of Interior region = Number of edges enclosing that region
- Degree of Exterior region = Number of edges exposed to that region
Here, this planar graph splits the plane into 3 regions- R1, R2, and R3 where-
Degree (R1) = 3
Degree (R2) = 3
Degree (R3) = 4
Planar Graph Chromatic Number
The Chromatic Number of any planar graph is always less than or equal to 4. Thus, any planar graph always requires a maximum of 4 colors for coloring its vertices.
Planar Graph Properties
Property 2: The sum of all the degrees of the regions is twice the number of edges in the graph.
Property 3: If G is a Planar graph with ‘e’ edges, ‘v’ vertices and ‘r’ number of regions in the planar representation of G, then-
r = e – v + 2
This is called Euler’s Formula and remains the same in all the planar representations of the graph.
Property 4: If G is a planar graph with k components, then-
r = e – v + (k + 1)
Property 5: If a connected planar graph G has e edges and v vertices, then 3v-e≥6.
Example: Prove that complete graph K4 is planar.
The complete graph K4 contains 4 vertices and 6 edges.
We know that for a connected planar graph 3v-e≥6.Hence for K4, we have 3×4-6=6 which satisfies the property (3).
Thus K4 is a planar graph. Hence Proved.
Property 6: A complete graph Kn is a planar if and only if n<5.
Property 7: A complete bipartite graph Kmn is planar if and only if m<3 or n>3.
Non-planar Graph
A graph is defined as a non-planar graph if it can be drawn in a plane with edges that intersect each other.
In other words, It can be drawn in such a way that edges should cross each other.
Example: Show that K5 is non-planar.
The complete graph K5 contains 5 vertices and 10 edges.
Now, for a connected planar graph 3v-e≥6.
Hence, for K5, we have 3 x 5-10=5 (which does not satisfy property 3 because it must be greater than or equal to 6).
Thus, K5 is a non-planar graph.
Applications of Graph Coloring
Some applications of graph coloring include:
- Register Allocation
- Map Coloring
- Bipartite Graph Checking
- Mobile Radio Frequency Assignment
- Making a time table, etc.
Handshaking Theorem
The sum of degrees of all the vertices in a graph G is equal to twice the number of edges in the graph.
Mathematically it can be stated as:
∑v∈Vdeg(v)=2e
Proof: Let G = (V, E) be a graph where V = {v1,v2, . . . . . . . . . .} be the set of vertices and E = {e1,e2 . . . . . . . . . .} be the set of edges. We know that every edge lies between two vertices so it provides degree one to each vertex. Hence each edge contributes degree two for the graph. So the sum of degrees of all vertices is equal to twice the number of edges in G.
Hence, ∑v∈Vdeg(v)=2e
Subgraph
A graph G’ is said to be a subgraph if it is extracted from graph G where the set of vertices and edges are subsets of graph G.
In other words, if all the vertices and edges of a graph G’ belong to G, and each edge of G’ has the same end vertices in G’ as in G.
Original Subgraph
A graph by deleting the edge between V4 and V5.
A graph by deleting the edge between V4 and V5.
A graph by deleting the edge between V2 and V3.
A graph by deleting the edge from V2 to V4.
Additional Cases
Case 1: In any planar graph, if degree of each region is K, then-
K x |R| = 2 x |E|
Case 2: In any planar graph, if degree of each region is at least K (>=K), then-
K x |R| <= 2 x |E|
Case 3: In any planar graph, if degree of each region is at most K (<=K), then-
K x |R| >= 2 x |E|
Points to remember:
- Vertex and edge sets are subsets of those of G
- a supergraph of a graph G is a graph that contains G as a subgraph.
- A graph G contains another graph H if some subgraph of G
- is H or
- is isomorphic to H.
- H is a proper subgraph if H!=G
Spanning Tree
In graph theory, a spanning tree is a subgraph that is a tree which includes all of the vertices of G. If a vertex is missed, then it is not a spanning tree.
In other words, a spanning tree is a subgraph of G, which includes all the vertices of G with (n-1) edges. Where ‘n’ is no. of vertices. All the possible created spanning trees from the original graph would have the same no. of vertices but the no. of edges would be (n-1).
Original Spanning tree
The total number of spanning trees with n vertices that can be created from a complete graph is equal to n power (n-2).
If we have n = 5, the maximum number of possible spanning trees is equal to 5 power (5-2) = 125. Thus, 125 spanning trees can be formed from a complete graph with 5 vertices.
Fig – Spanning tree 1
Fig – Spanning tree 2
Fig – Spanning tree 3
Points to remember:
- Subgraph H has the same vertex set as G
- Possibly not all the edges
- “H spans G”
Theorem: A graph is connected if and only if it has a spanning tree.
Proof: Let G be a connected graph. Delete edges from G that are not bridges until we get a connected subgraph H in which each edge is a bridge. Then H is a spanning tree. On the other hand, if there is a spanning tree in G, there is a path between any pair of vertices in G; thus G is connected.
Applications of the Spanning Tree
Basically, a spanning tree is used to find a minimum path to connect all nodes of the graph. Some of the common applications of the spanning tree are listed as follows –
- Cluster Analysis
- Civil network planning
- Computer network routing protocol
Properties of Spanning Tree
- There can be more than one spanning tree of a connected graph G.
- A spanning tree has n-1 edges, where ‘n’ is the number of nodes.
- There can be a maximum n power (n-2) number of spanning trees that can be created from a complete graph.
- A spanning tree does not have any cycles or loop.
- A spanning tree is connected with least no. of edges, so removing one edge from the tree will make the graph disconnected.
- A spanning tree is maximally acyclic, so adding one edge to the tree will create a loop.
- If the graph is a complete graph, then the spanning tree can be constructed by removing maximum (e-n+1) edges, where ‘e’ is the number of edges and ‘n’ is the number of vertices.
So, a spanning tree is a subset of connected graph G, and there is no spanning tree of a disconnected graph.
Minimum Spanning Tree
A graph is said to be a minimum spanning tree, if the sum of all the weights of the edges is minimum. The weight of the spanning tree is the distance assigned to each edge connected to the vertices.
Original Minimum Spanning tree
As per the statement, Fig – 2 has the lowest sum of all the edges weight among all the Minimum Spanning tree, therefore Fig – 2 is the Minimum Spanning tree.
Applications of Minimum Spanning Tree
The applications of the minimum spanning tree are given as follows –
- Minimum spanning trees can be used to design water-supply networks, telecommunication networks, and electrical grids.
- Majorly, spanning trees are used to find paths in the map.
Algorithms for Minimum Spanning Tree
A minimum spanning tree can be found from a weighted graph by using the algorithms given below –
- Prim’s Algorithm
- Kruskal’s Algorithm
Prim’s algorithm
It is a greedy algorithm that starts with an empty spanning tree. It is used to find the minimum spanning tree from the graph. This algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.
Kruskal’s algorithm
This algorithm is also used to find the minimum spanning tree for a connected weighted graph. Kruskal’s algorithm also follows a greedy approach, which finds an optimum solution at every stage instead of focusing on a global optimum.
Note: Later, in upcoming lesson, you will learn in detail about Prim’s & Kruskal’s algorithm,
Vertex Induced Graph
An induced subgraph formed from some of the vertices and all the edges (from the original graph) connecting pairs of vertices in the original graph.
Original Vertex Induced Graph
Edge Induced Graph
An induced subgraph formed from some of the edges (from the original graph) and the vertices that are at their endpoints.
Original Edge Induced Graph
If you find anything incorrect in the above-discussed topic and have further questions, please comment below.
Connect on:
