Graph theory : How to find edges ??

2.9k Views Asked by At

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?

1

There are 1 best solutions below

4
On BEST ANSWER

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.