2
$\begingroup$

Let $n$ be an even positive integer and $K_{2n}$ be the complete graph on $2n$ vertices. There are $\dfrac{1}{2}{{2n}\choose n}={{2n-1}\choose n}$ subgraphs of $K_{2n}$ which is isomorphic to $K_{n,n}$ and we use $E_1,E_2,\dots,E_{{2n-1}\choose n}$ to denote the edge sets of the ${2n-1}\choose n$ subgraphs respectively.

My question is whether I can partition the edge set of $K_{2n}$ to $S_1,S_2,\dots,S_{2n-1}$ such that $|S_i|=n$ for every $1\leq i\leq2n-1$ and $\{\cup^{n}_{k=1}S_{i_k}:1\leq i_1<i_2<\dots<i_n\leq 2n-1\}=\{E_1,E_2,\dots,E_{{2n-1}\choose n}\}$?

$\endgroup$

2 Answers 2

4
$\begingroup$

No, this is not possible. Towards a contradiction, suppose such a partition $S_1, \dots, S_{2n-1}$ of $E(K_{2n})$ exists. I first claim that each $S_i$ must be a matching. If not, then some vertex $v$ has degree at least 2 in say $S_1$. But now if we sort the $S_i$ according to the degree of $v$ in $S_i$ and pick the $n$ largest ones, then the union of these $S_i$ will not be isomorphic to $K_{n,n}$ since $v$ will have degree larger than $n$.

Since each $S_i$ is a matching, each $S_i$ determines a bipartition of $V(K_{n,n})$. We may suppose that $S_1$ and $S_2$ determine different bipartitions. But now, no collection of $S_i$s containing both $S_1$ and $S_2$ can induce a copy of $K_{n,n}$.

$\endgroup$
0
2
$\begingroup$

If $n\geq 3$, then there are three sets (say, $S_1$, $S_2$, $S_3$ --- some may coincide) containing the edges of some triangle $v_1v_2v_3$. Then any collection of $S_i$ containing $S_1$, $S_2$, $S_3$ gives a non-bipartite graph.

On the other hand, for $n=1,2$ this is possible. An example for $n=1$ is trivial; for $n=2$ it is provided by $S_1=\{12,34\}$, $S_2=\{13,24\}$, $S_3=\{14,23\}$.

$\endgroup$

You must log in to answer this question.

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