Let G be a bipartite graph.

Question

Let G be a bipartite graph.If a21 is the transpose of A21, show that the vertices of G can be partitioned. So that the adjacency matrix of G has the following form:

\(\begin{bmatrix} 0 & A_12  \\ A_21 & 0   \\ \end{bmatrix}\)

Summary

There is a graph G which has total vertices 6. Where 6 vertices are divided into sets of two such as now we have {1,2,3} and {4,5,6}. After that there is a adjacency matrix which is to be obtaining the matrices A₁₂ and A₂₁ where A₁₂ = (A₂₁)^T.

Explanation

In this graph, vertices are divide into two sets naming U and V. Where either the edge of every U will get connect to V or the edge of every V is connected to U. This is what we called as a Bipartite Graph. But there should not be a single edge that should connect to itself or to the same set.

In the above diagram, we can see the Bipartite graph.

In the adjacency matrix, we will look for the block matrix form as shown in the below matrix

\(\begin{bmatrix} 0_r,_r & B  \\ B_T & 0_s,_s \\ \end{bmatrix}\)

We will see the solution below

Let’s consider the graph:
G=
Here the two independent sets of vertices are:
{1,2,3} and {4,5,6}
Ajaceny matrix:

A=\(\begin{bmatrix} 0&0&0&1&1&0 \\0&0&0&1&1&0\\0&0&0&0&1&1\\ 1&1&0&0&0&0\\1&1&1&0&0&0\\0&0&1&0&0&0\end{bmatrix}\)= \(\begin{bmatrix} 0 & A_12  \\ A_21 & 0 \\ \end{bmatrix}\)

Where, A₁₂ = \(\begin{bmatrix} 1&1&0 \\ 1&1&0\\o&1&1 \end{bmatrix}\)

A₂₁ =\(\begin{bmatrix} 1&1&0 \\ 1&1&1\\0&0&1 \end{bmatrix}\)

A₂₁ = (A₁₂ )^T

Therefore now it is proved.