Question

How many non-isomorphic connected bipartite simple graphs are there with four vertices?

Short answer

There are three connected bipartite simple graphs showing non-isomorphism.

Step-by-step solution

Concept/Significance of bipartite graph

Bipartite graphs are those that are separated into two groups of nodes, with no two neighboring nodes in the same set.

Determination of the number of non-isomorphic connected bipartite simple

Consider a four-vertices connected bipartite graph.

A connected bipartite graph is a graph in which the vertex set is divided into two subsets, each with m and n vertices, where\({K_{m,n}}\)is the symbol for the graph.

Assume that the vertex set 4 is divided into two subsets of one and three vertices each.

Then,\({K_{1,3}}\)is the only connected bipartite simple graph with these pieces. The graph is as shown below.

From observation, we find that the above graph does not follow the one-to one property. So, the \({K_{1,3}}\) is non-isomorphic.

Let's say the vertex set 4 is divided into two subsets, each with two vertices. Then there will be two bipartite simple graphs connected with portions of these sizes two vertices each . The following are the graphs of these two linked bipartite simple graphs with one edge removed.

The one-to-one property is violated by the graphs. So, these \({K_{2,2}}\) graphs are non-isomorphic.

Thus, there are three connected bipartite simple graphs showing non-isomorphism.