2
$\begingroup$

So.. Perhaps I'm misunderstanding this question, but it reads:

How many nonisomorphic complete bipartite graphs $G = (V, E)$ satisfy $|V| = n \geq 2$?

I mean.. Doesn't this just ask how many complete bipartite graphs have 2 or more vertices, of which there are infinitely many? I think I must be missing something.

  • 2
    $\dots$ as a function of $n$.2012-11-13

2 Answers 2

4

Hint: Two complete bipartite graphs on $n$ vertices are nonisomorphic if and only if their partite sets are of different sizes. How many ways can $n$ be written as the sum of two non-negative integers in which the order of the summands does not matter?

2

First, count the case where one partition is the empty set, the other partition contains $n$ vertices, and there are no edges.

Then, for even $n$ there are $\dfrac{n}{2}$ graphs that are non-isomorphic. For odd $n$ there are $\dfrac{n-1}{2}$ graphs that are non-isomorphic (in odd graphs, there is no case where both partitions have $\dfrac{n}{2}$ vertices).

So, it can be said that for any $n \geq 2$ there are $\dfrac{n}{2} + 1$ graphs (rounding down) $G=(V,E)$ that satisfy $|V| = n$