# Graph theory : How to find edges ??

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?

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

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.

• 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.
– Mora
Mar 27 '14 at 14:53
• For b) km,n bipartition (x,y) therefore # of edges from 0 vertex in x to y is 'n', So total # of edges = mn
– Mora
Mar 27 '14 at 14:56
• @Mora You got it! Mar 27 '14 at 15:12
• Thank you so much that was really useful !
– Mora
Mar 27 '14 at 15:13