2
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I can form a total of 64 graphs with 4 vertices and I think there are only 4 graphs with an odd cycle. $\endgroup$
    – davidaap
    Commented Feb 26, 2020 at 14:39
  • $\begingroup$ @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. $\endgroup$
    – davidaap
    Commented Feb 26, 2020 at 14:57
  • $\begingroup$ oh, sorry, I may have to specify that. I was talking about labeled graphs. $\endgroup$
    – davidaap
    Commented Feb 26, 2020 at 15:04
  • $\begingroup$ Ok. So there are $64$ total graphs, and there are $4! = 24$ odd cycle graphs (permute the labels). Thus, the answer is $40$. $\endgroup$ Commented Feb 26, 2020 at 15:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .