Counting the number of bipartite graph with 4 vertices.

1k Views Asked by At

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?

1

There are 1 best solutions below

4
On BEST ANSWER

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.