0
$\begingroup$

I'm attempting to solve a problem that I think can be solved best with graph theory. I know very little regarding graph theory, so excuse any misuse of vocabulary (which I only picked up in the last hour or so).

As the title states, given a set of $n$ distinct vertices and $k \in \mathbb{Z}$, I'm trying to find how many $k$-regular bipartite graphs I can make. If it's significantly simpler, in the problem I'm trying to solve, $k = 1$.

Even if you straight up give the answer, I would not mind references, literature, and other learning material. I've always found graph theory to be interesting, and I think this is a good way to break into it.

$\endgroup$
0
$\begingroup$

It sounds like a matching. That is, each vertex is paired up with exactly one other vertex. If $n$ is odd, then this is not possible for $k = 1$. Note that the Handshake Lemma states that the sum of the vertex degrees is twice the number of edges. So $nk = 2E$. If $k = 1$ and $n$ is odd, then $nk$ is not even.

So suppose $n$ is even. If your graph is complete (all vertices are adjacent), we stat by choosing our first two vertices to match. This can be done in $\binom{n}{2}$ ways. That is, choose the first vertex. Then there are $n-1$ remaining vertices to match it with. Since we could have chosen the second vertex first, order doesn't matter so we divide out by $2$. We repeat for the remaining $n-2$ vertices. The formula is:

$$\sum_{i=0}^{n/2} \binom{n - 2i}{2}$$

This assumes $n$ is even.

If you have a more specific case, the count will be more restrictive.

http://en.wikipedia.org/wiki/Matching_%28graph_theory%29

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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