Regular and Bipartite graphs

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.

Solution:

The Euler’s circuit for the above graph is:

V₁, V₂, V₃, V₅, V₂, V₄, V₇, V₁₀, V₆, V₃, V₉, V₆, V₄, V₁₀, V₈, V₅, V₉, V₈, V_1. 

 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!”