Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
4  
Fix a specific $n \geq 2$ and see how many complete bipartite graphs have that cardinality. –  Deven Ware Nov 13 '12 at 19:52
2  
$\dots$ as a function of $n$. –  Hendrik Jan Nov 13 '12 at 20:05

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.