Skip to main content
2 of 2
Commonmark migration

A specific collection of subgraphs in $K_{70, 70}$

Does there exist a collection of subgraphs $\{\Gamma_i\}_{i = 1}^{24}$ of $K_{70, 70}$, that satisfy the following two properties:

1)$\Gamma_i \cong K_{i, i} \forall 1 \leq i \leq 24$;

2)Any edge of $K_{70, 70}$ belongs to exactly one subgraph from this collection?

This question appeared because, the $K_{n, n}$ always has $n^2$ vertices, and $70^2 = \Sigma_{i = 1}^{24} i^2$. Thus the numbers of edges here match perfectly. But that is clearly not enough...

Both the initial graph and the collection of subgraphs are too large to solve this question via brute force. And I do not know any other way to approach this problem.

Any help will be appreciated.

Chain Markov
  • 2.6k
  • 15
  • 26