0
$\begingroup$

A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. We denote by Kn the complete graph on n vertices. A simple bipartite graph with bipartition (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 Km,n.

(a) How many edges does Kn have?

(b) How many edges does Km,n have?

$\endgroup$
4
  • $\begingroup$ Can you make a start on these problems? $\endgroup$
    – Gerry Myerson
    Mar 27, 2014 at 12:13
  • $\begingroup$ @GerryMyerson i got # of ways are nc2 = n(n-1)/2 edges and So total # of edges = mn $\endgroup$
    – Mora
    Mar 27, 2014 at 15:07
  • $\begingroup$ Then you got the right answers. So, why the question? $\endgroup$
    – Gerry Myerson
    Mar 27, 2014 at 23:46
  • 1
    $\begingroup$ i got the right answer after @Nicholas R. Peterson gave me the hint. $\endgroup$
    – Mora
    Mar 28, 2014 at 0:34

1 Answer 1

Reset to default
2
$\begingroup$

Hint:

$K_n$ has exactly one edge for each unordered pair of distinct vertices.

$K_{m,n}$ has exactly one edge for each pair $(x,y)$ of vertices such that $x\in X$ and $y\in Y$.

So, if you can count those pairs, you can count the edges.

$\endgroup$
4
  • 1
    $\begingroup$ i found out for question a that you can get the edges by choosing two vertices in Kn. therefore # of ways are nc2 = n(n-1)/2 edges. $\endgroup$
    – Mora
    Mar 27, 2014 at 14:53
  • 1
    $\begingroup$ For b) km,n bipartition (x,y) therefore # of edges from 0 vertex in x to y is 'n', So total # of edges = mn $\endgroup$
    – Mora
    Mar 27, 2014 at 14:56
  • $\begingroup$ @Mora You got it! $\endgroup$
    – Nick Peterson
    Mar 27, 2014 at 15:12
  • $\begingroup$ Thank you so much that was really useful ! $\endgroup$
    – Mora
    Mar 27, 2014 at 15:13

You must log in to answer this question.

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