Talk:Complete bipartite graph

Possible error in the vertex and edge covering numbers. The edge covering number should be equal to vertex covering number, right? F.ex. if you look the $K_{2,3}$, you will see that the edge covering number is two, as is vertex covering number. You might want to also add the k(G) and k'(G) terms in there.

Atuomi (talk) 13:30, 21 November 2007 (UTC)

Is there a way to display the images so that they don't appear in boxes? The border of the box interferes with the image. McKay 04:51, 1 June 2006 (UTC)

proof for number of trees in a bipartite graph

The proof for m^n-1.n^m-1 as the number of spanning trees in a bipartite graph:
1. we know for sure that such a tree will have m+n-1 arcs
2. we assume the m+n-1 "sticks" are veritcally placed
so we have
||||||..m+n-1 times
3. we assume all the ms are placed on top and the ns are placed below
4. to fill up the tree vertices, we 1st try to place all the m's on top and the n's on the bottom
assume there are "m" ms and "n" ns
we can place the ms on top so that each m is chosen once in m! ways this keeps "n-1" tops on the stick empty which can be chosen in m^(n-1) ways
Likewise for the ns below we can chose the 1st lot in n! ways and the remaining in n^(m-1) ways:

m1m2m3..mm //m m m.....n times = m!.m^n-1
| | | | | | |
n1n2..nn//n.n.n.n......m times=n!.n^m-1

Now we see that the 1st m!.n! set is always common in all the trees and it is the remaining m^n-1.n^m-1 which decides the orientation and shape of the graph/tree so formed
example say we have m1,m2,m3 // n1 n2, m!.n!=12
we get
Set 1

m!n!part   m^n-1.n^m-1 part remains fixed

(m1n1,m2n2)(m3n1,m1n1)
(m1n2,m2n1)(m3n1,m1n1)<--valid spanning tree
(m2n1,m1n2)(m3n1,m1n1)<--same as above
(m2n2,m1n1)(m3n1,m1n1)

(m3n1,m2n2)(m1n1,m1n1)
(m3n2,m2n1)(m1n1,m1n1)
(m2n1,m3n2)(m1n1,m1n1)
(m2n2,m3n1)(m1n1,m1n1)

(m1n1,m3n2)(m2n1,m1n1)
(m1n2,m3n1)(m2n1,m1n1)<--same as above
(m3n1,m1n2)(m2n1,m1n1)<--same as above
(m3n2,m1n1)(m2n1,m1n1)

so the set of 12 gives 3^0 =1 spanning trees
i.e for a fixed value of the m^n-1 .m^n-1 combo m!.n! gives 1 tree so for each combo of m^n-1.n^m-1 we will get 1 spanning tree each
(example put n1=n2 in the m^n-1.n^m-1 under the 1st part)
Hence the pattern can easily be shown to repeat for any m and n