Skip to main content
Commonmark migration
Source Link

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.

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.

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.

Source Link
Chain Markov
  • 2.6k
  • 15
  • 26

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.