# graph theory bi-partitions

A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. We denote by K(n) the complete graph on n vertices.

A simple bipartite graph with bi-partition (X,Y) such that every vertex of X is adjacent to every vertex of Y is called a complete bipartite graph. If |X| = m and |Y| = n, we denote this graph with K(m,n).

(a) How many edges does K(n) have?
(b) How many edges does K(m,n) have?


This is what I've got so far: as I understand this |X| = m, m is the number of vertices, each of them has an edge to every vertex from Y. So K(m,n) should have m*n edges. am i not understanding this right?

As for (a) i'm not really sure.

-

Yes, you are right about $K_{mn}$.

You can solve both $(a)$ and $(b)$ by applying the Hanshaking Lemma: the sum of the degrees is twice the number of edges.

Otherwise, for $(a)$ chose the first vertex (how many choices?), chose the second vertex (how many choices?) and pay attention to the double counting....

-
so if there are n vertice, does that mean that each has a degree of (n-1)? since every vertex is connected to every other vertex? So is the answer ((n-1)*n)/2 – Supernatural Apr 25 '13 at 1:29
@Supernatural Yup. – N. S. Apr 25 '13 at 2:03

Do you know that the sum of the degrees of the vertices of a graph gives twice the number of edges?

-
do you mean completed graph? – Supernatural Apr 25 '13 at 1:24