Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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....

share|improve this answer
    
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?

share|improve this answer
1  
do you mean completed graph? –  Supernatural Apr 25 '13 at 1:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.