# Counting the number of bipartite graph with 4 vertices.

I know this may sound like a simple question, as you can count all the bipartite graph in this case. Let $$U$$ and $$V$$ be the parts of the bipartite graph. If you put 2 vertices in $$U$$ and 2 vertices in $$V$$, then you would have a total of 9 bipartite graphs according to this answer.

Now, I am confused when we have 1 vertex in $$U$$ and 3 vertices in $$V$$. In this case, we would have only one bipartite graph, as we need every vertex in $$V$$ to be connected to at least one vertex in $$U$$. But if we change roles, that is, 3 vertices in $$U$$ and 1 vertex in $$V$$, then we would have $$2^3-1=7$$ bipartite graphs. So how should we count the number of bipartite graphs in this simple example?

Hint: A graph is bipartite if and only if it has no odd cycles. Since we only have four vertices, the only way that a graph cannot be bipartite is if it has a cycle of length $$3$$.

Now, answer the two following questions:

$$1$$) How many total graphs are there on four vertices?

$$2$$) How many ways can you form a graph on $$4$$ vertices with an odd cycle?

Once you figure out these quantities, your answer is just $$(1) - (2)$$, where $$(1)$$ is the answer to the first question I asked, and $$(2)$$ is the answer to the second question I asked.

• I can form a total of 64 graphs with 4 vertices and I think there are only 4 graphs with an odd cycle. Commented Feb 26, 2020 at 14:39
• @EkeshKumar I think there are more than 3 or 4 actually. If I label the vertices A, B, C and D, then we would have: A-B-C-A, A-C-D-A, A-B-D-A and B-C-D-B. However, for example, in the first case, we can attach D to A or to B or to C or we simply let it be isolated. In that case we would have four more cases. The same with A-C-D-A, A-B-D-A and B-C-D-B. Commented Feb 26, 2020 at 14:57
• oh, sorry, I may have to specify that. I was talking about labeled graphs. Commented Feb 26, 2020 at 15:04
• Ok. So there are $64$ total graphs, and there are $4! = 24$ odd cycle graphs (permute the labels). Thus, the answer is $40$. Commented Feb 26, 2020 at 15:27