2
$\begingroup$

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.

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Supernatural
    Apr 25, 2013 at 1:29
  • $\begingroup$ @Supernatural Yup. $\endgroup$
    – N. S.
    Apr 25, 2013 at 2:03
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ do you mean completed graph? $\endgroup$
    – Supernatural
    Apr 25, 2013 at 1:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .