bipartite graph

Question

a)G={V,E} be bipartite graph and vertex partition V={V1, V2} if suppose number of vertices in V1 is 3 and V2 is 4 then number of bipartite graphs from V1 to V2 is ____________

b)G={V,E} be bipartite graph and vertex partition V={V1, V2} if suppose number of vertices in V1 is 3 and V2 is 4 then number of  complete bipartite graphs from V1 to V2 is ____________

Answer 1

Let  V1 partition contains m vertices and V2 partition contains n vertices..

Hence maximum number of edges possible =  n + n + n ......(m times) [ Every vertex of v1 will be connected every other vertex of V2 but not connected within the partition]    =  mn

This also corresponds to complete bipartite graph which is referred as K_m,n and hence unique..

Hence number of complete bipartite graphs  =  1

Now as far as bipartite graph is concerned :

For each of the above mn edges , an edge can either be selected or rejected and hence has 2 choices

So no of bipartite graphs =  no of ways the edges can be selected

                                    =   2 * 2 * 2.................(mn) times

                                    =   2^mn  graphs

Substituting   m  =  3 and  n  =  4 , we have :

No of bipartite graphs    =   2^3*4

                                   =  2¹² graphs..

This also includes the case where we have no edges..

A graph having no edges is trivially bipartite as we can partition the vertex set into 2 disjoint sets without restriction..