Bipartite graphs

Complete Graph

A graph G is said to be complete if every vertex in G is connected to every other vertex in G. Thus a complete graph G must be connected. The complete graph with n vertices is denoted by K_n. The Figure shows the graphs K₁ through K₆.

Regular Graph:

A graph is said to be regular or K-regular if all its vertices have the same degree K. A graph whose all vertices have degree 2 is known as a 2-regular graph. A complete graph K_n is a regular of degree n-1.

Example1: Draw regular graphs of degree 2 and 3.

Solution: The regular graphs of degree 2 and 3 are shown in fig:

Example2: Draw a 2-regular graph of five vertices.

Solution: The 2-regular graph of five vertices is shown in fig:

Example3: Draw a 3-regular graph of five vertices.

Solution: It is not possible to draw a 3-regular graph of five vertices. The 3-regular graph must have an even number of vertices.

Bipartite Graph:

A graph G=(V, E) is called a bipartite graph if its vertices V can be partitioned into two subsets V₁ and V₂ such that each edge of G connects a vertex of V₁ to a vertex V₂. It is denoted by K_mn, where m and n are the numbers of vertices in V₁ and V₂ respectively.

Example: Draw the bipartite graphs K₂, 4and K₃ ,4.Assuming any number of edges.

Solution: First draw the appropriate number of vertices on two parallel columns or rows and connect the vertices in one column or row with the vertices in other column or row. The bipartite graphs K_2,4 and K_3,4 are shown in fig respectively.

Complete Bipartite Graph:

A graph G = (V, E) is called a complete bipartite graph if its vertices V can be partitioned into two subsets V₁ and V₂ such that each vertex of V₁ is connected to each vertex of V₂. The number of edges in a complete bipartite graph is m.n as each of the m vertices is connected to each of the n vertices.

Example: Draw the complete bipartite graphs K_3,4 and K_1,5.

Solution: First draw the appropriate number of vertices in two parallel columns or rows and connect the vertices in the first column or row with all the vertices in the second column or row. The graphs K_3,4 and K_1,5 are shown in fig:

Euler Path:

A Euler Path through a graph is a path whose edge list contains each edge of the graph exactly once.

Euler Circuit: An Euler Circuit is a path through a graph, in which the initial vertex appears a second time as the terminal vertex.

Euler Graph: An Euler Graph is a graph that possesses a Euler Circuit. A Euler Circuit uses every edge exactly once, but vertices may be repeated.

Example: The graph shown in fig is a Euler graph. Determine Euler Circuit for this graph.

Solution: The Euler Circuit for this graph is

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

We can produce an Euler Circuit for a connected graph with no vertices of odd degrees.

State and Prove Euler's Theorem:

Statement: Consider any connected planar graph G= (V, E) having R regions, V vertices and E edges. Then V+R-E=2.

Proof: Use induction on the number of edges to prove this theorem.

Basis of Induction: Assume that each edge e=1.Then we have two cases, graphs of which are shown in fig:

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

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

Hence, the basis of induction is verified.

Induction Step: Let us assume that the formula holds for connected planar graphs with K edges.

Let G be a graph with K+1 edge.

Firstly, we suppose that G contains no circuits. Now, take a vertex v and find a path starting at v.Since G is a circuit free, whenever we find an edge, we have a new vertex. At last, we will reach a vertex v with degree1. So we cannot move further as shown in fig:

Now remove vertex v and the corresponding edge incident on v. So, we are left with a graph G* having K edges as shown in fig:

Hence, by inductive assumption, Euler's formula holds for G*.

Now, since G has one more edge than G*, one more vertex than G* with same number of regions as in G*. Hence, the formula also holds for G.

Secondly, we assume that G contains a circuit and e is an edge in the circuit shown in fig:

Now, as e is the part of a boundary for two regions. So, we only remove the edge, and we are left with graph G* having K edges.

Hence, by inductive assumption, Euler's formula holds for G*.

Now, since G has one more edge than G*,one more region than G* with same number of vertices as G*. Hence the formula also holds for G which, verifies the inductive steps and hence prove the theorem.