Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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?

share|cite|improve this answer

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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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