2

This is the solution to the question.

enter image description here

But I don't get why's that when a=b, "the same subgraph will also be selected by interchanging A and $A^{'}$", but it's not the case when a not equal to b?

From my understanding, $K_{a,b}$ is a bipartite graph, whether the set A is on the left or right side, the edges are connected the same way, isn't it?

1 Answers1

3

To be concrete, consider the number of $K_{2,2}$ subgraphs in $K_4$. One such subgraph can be obtained by taking $A = \{v_1, v_2\}$ and $A' = \{v_3, v_4\}$. If we weren't careful, we'd also count $A = \{v_3, v_4\}$ and $A' = \{v_1, v_2\}$ as giving another $K_{2,2}$ subgraph -- but "both" of these subgraphs have the same vertex set and the same edge set, so we've really just counted the same subgraph twice.