Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Types of Graphs
2.1.
Complete Graph
2.2.
Regular Graph
2.3.
Bipartite Graph
2.4.
Complete Bipartite Graph
3.
Euler Path
3.1.
 Statement and Proof of Euler's Theorem
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Regular and Bipartite graphs

Author Naman Kukreja
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Nowadays, data is everything, so much research is going on in data analysis and data representation. Graphs are convenient and easy to understand Data Structures to represent data.

Graphs contain nodes that store data and edges connecting those nodes or vertices. Here we will learn about some of the different types of the graph like regular, complete, bipartite, etc., in detail and with examples.

So without wasting any further time, let's get on with our topic.

Types of Graphs

There are many types of graphs, but here we will discuss some of them: complete graph, regular graph, bipartite graph, and complete bipartite graph.

Complete Graph

Graph G, which has every vertex connected to every other vertex in the same graph G, is a complete graph. The complete graph is connected. The images below show the complete graphs starting from one vertex to six vertices.

Regular Graph

Graph G, in which all the vertices have the same degree K is known as a regular graph. A graph in which all the vertices have degree 2 is known as a 2- regular graph, and a complete graph, Kn is a regular graph of degree n-1.

Let’s discuss more regular graphs with the help of examples.

Example 1: Draw regular graphs for both degree 2 and degree 3.

Solution: The images below show the two regular graphs of degrees 2 and 3.

The left is degree 2, and the right image is a regular graph with degree 3.

Example 2: Draw a graph with five vertices and have degree 2.

Solution: The image below shows a regular graph with five vertices and degree 2.

Example 3: Draw a regular graph with five vertices and degree 3.

Solution: Drawing a regular graph with degree 3 of odd vertices is impossible. The number of vertices must be even as we have outlined for the six vertices below:

Bipartite Graph

A bipartite graph G=(V, E) has vertices V that may be partitioned into two subsets, V1 and V2, with each edge of G connecting a vertex of V1 to a vertex of V2. Kmn is the symbol for it, where m and n are the vertices in V1 and V2, respectively.

We will learn more about the bipartite graphs with the help of examples: 

Example: Draw the bipartite graphs for k2,4 and k3,4. You can assume any number of edges.

Solution: Below is the representation of both parts of the above question.

Complete Bipartite Graph

Suppose the vertices V of a graph G = (V, E) can be partitioned into two subsets, V1 and V2, each vertex of V1 being linked to each vertex of V2. The graph is termed a full bipartite graph. Because each of the m vertices is connected to each of the n vertices, a complete bipartite graph has m.n edges.

We will learn more about the complete bipartite graphs with the help of examples: 

Example: Draw the complete bipartite graph for K1,5 and K3,4.

Solution: The first image will show the complete bipartite graph of K1,5, and the second image shows K3,4.

                                        K1,5

K 3,4

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Euler Path

An Euler path is a list that contains all the edges of a graph exactly once.

We will learn some terms before directly moving on to examples.

Euler Circuit: In a normal Euler list, all the edges appear only once, but in the Euler circuit, the initial edge also comes at last in place of the terminal edge to make a list a closed circuit.

Euler Graph: The graph which possesses an Euler circuit is known as Euler Graph.

Example: Given the graph below. Write its Euler’s circuit.

Euler's circuit

Solution:

The Euler’s circuit for the above graph is:

V1, V2, V3, V5, V2, V4, V7, V10, V6, V3, V9, V6, V4, V10, V8, V5, V9, V8, V1. 

 Statement and Proof of Euler's Theorem

Statement: Consider any linked planar network with R regions, V vertices, and E edges, G= (V, E). V+R-E=2 in this case.

Proof: We will use induction to prove this using number of edges.

Basic of induction: Assume the number of the edges is one that will lead to two cases which are given below.

In Fig: we have R=1 and V=1. Thus 1+2-1=2.

In Fig: we have R=1 and V=2. Thus 2+1-1=2

Hence induction is verified.

Induction Step: 

We can assume that it will hold for a graph with k edges. Now we will take a graph with K+1 edges.

To begin, we assume that G is devoid of circuits. Take a vertex v and create a route that starts at v. We have a new vertex every time we locate an edge in G since it is a circuit-free language. Finally, we'll arrive at a vertex v of degree 1. As a result, we are unable to proceed as depicted in fig:

Remove the matching edge incident on v and the vertex v. As a result, we get a graph G* with K edges, as illustrated in fig:

As a result, Euler's formula holds for G* by inductive assumption.

Now, G has one more edge than G* and one more vertex and the same number of regions as G*. As a result, the formula also applies to G.

Second, we suppose that G comprises a circuit and that e is an edge in the circuit shown in the figure:

Now, since e is a portion of a two-region border, as a result, we merely delete the edge, leaving us with a graph G* with K edges.

As a result, Euler's formula holds for G* by inductive assumption.

G now has one more edge than G* and one more area with the same number of vertices as G*. As a result, the formula also holds for G, proving the thesis by verifying the inductive stages.

Also see Application of graph data structure

FAQs

1. A triangle-free graph with n vertex contains how many edges?
A triangle-free graph with n vertex contains (n^2)/4 edges.
 

2. Which graph has all the vertexes of the first set connected to all the vertexes of the second set?
The Complete Bipartite Graph has the property in which all the vertices of the first set are connected with the vertices of the second set.
 

3. What is the relation between a complete bipartite graph and a modular graph?
The relation between a complete bipartite graph and a modular graph is that every complete bipartite graph is modular.
 

4. What is the other name of the complete bipartite graph?
A complete bipartite graph is also known as a biclique graph.

Key Takeaways

In this article, we have extensively discussed different graphs like the regular graph, complete graph, bipartite graph, and complete bipartite graph. To understand these better, we have used examples, and along with this, we also discussed Euler’s path different terminologies connected to it with its statement and proof.
Check out this problem - No of Spanning Trees in a Graph

If you want to learn more about different graphs, you must read this blog. You will get a complete idea about planar and non-planar graphs with proper examples. We hope that this blog has helped you enhance your knowledge regarding graphs and if you would like to learn more, check out our articles on Code studio. Do upvote our blog to help other ninjas grow.

 “Happy Coding!”

Live masterclass