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$ Mar 27 '14 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 '14 at 15:07
  • $\begingroup$ Then you got the right answers. So, why the question? $\endgroup$ Mar 27 '14 at 23:46
  • 1
    $\begingroup$ i got the right answer after @Nicholas R. Peterson gave me the hint. $\endgroup$
    – Mora
    Mar 28 '14 at 0:34
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 '14 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 '14 at 14:56
  • $\begingroup$ @Mora You got it! $\endgroup$ Mar 27 '14 at 15:12
  • $\begingroup$ Thank you so much that was really useful ! $\endgroup$
    – Mora
    Mar 27 '14 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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