# Bipartite Graph Counting.. Easy?

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.

-
Fix a specific $n \geq 2$ and see how many complete bipartite graphs have that cardinality. – Deven Ware Nov 13 '12 at 19:52
$\dots$ as a function of $n$. – Hendrik Jan Nov 13 '12 at 20:05

## 2 Answers

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?

-

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$

-