A 345-clique has 345*344/2=59340 edges.

59340 is not divisible by 21, making the <7,345>-partitioning problem unsolvable. It is impossible to partition a set of 59340 edges into disjoint sets each containing 21 edges.

We will prove the following more general theorem:

**Theorem 1:** If *m*=*p*^{k} and
*n*=*m*^{l} with prime *p* and natural
*k* and *l*, then a solution exists.

We will prove this theorem by creating an explicit partitioning solution.

If *m*=*p*^{k} and
*n*=*m*^{l} then one can find a finite field
*F* with *m* elements and a vector space *U* with
*n* elements over *F*.

Let the *n*-clique's vertices be the members of *U*. The subsets of
size *m* that will compose the *m*-cliques' vertices will be the
sets in *U* forming affine subspaces of dimension 1.

In other words, for every two elements *A* and *B* in *U*, such
that *A* isn't the zero element of *U*, we will use the elements
*Y* of *U* satisfying *Y*=*A**x*+*B*, for some
element *x* in *F* as vertices of an *m*-clique. There are
clearly exactly *m* such elements for every choice of *A* and
*B*, because there are *m* values that can be substituted for
each *x*, and if two of them yield the same *Y* then
*A**x*+*B*=*A**x*'+*B* can be solved to show
that *A* is the zero vector. Furthermore, every edge will appear in
exactly one *m*-clique because each edge signifies a pair of points in
*U* and each *m*-clique is a line in *U*: through each two
points passes exactly one line.

**Theorem 2:** For any prime *p* and any naturals *k* and *l*,
if *m*=*p*^{k}+1 and
*n*=(*p*^{k(l+1)}-1)/(*p*^{k}-1),
then the <*m*,*n*> partitioning problem has a
solution.

The simplest way to show this is by use of projective geometry. Consider the
vector space (*p*^{k})^{l+1}, minus the
zero element, where any two of the remaining elements are considered equivalent
if one is a scalar multiple of the other (a homothety relation). The projective
space now has
(*p*^{k(l+1)}-1)/(*p*^{k}-1)
different elements and any line in it (a 2D linear subspace in the original
vector space) has
(*p*^{2k}-1)/(*p*^{k}-1), or simply
*p*^{k}+1, elements.

However, for all unfamiliar with projective geometry, here is a construction that doesn't require it. We will prove the theorem, instead, by means of the following definition and two lemmas.

**Definition:** An <*m*,*n*> partitioning will be called
*separable* if the *n*(*n*-1)/*m*/(*m*-1)
*m*-cliques can be partitioned into (*n*-1)/(*m*-1) subsets, each
of size *n*/*m* in such a way that the vertices of the
*m*-cliques in each subset are pairwise disjoint.

**Lemma 1:** The <*m*,*n*> clique partitioning problem has
a solution if <*m*,(*n*-1)/(*m*-1)> has a solution and
<*m*-1,*n*-(*n*-1)/(*m*-1)> has a separable solution.

In order to prove this, we will construct the partitioning explicitly. This
is done by separating the *n* vertices into two sets. Set *A* will
contain (*n*-1)/(*m*-1) vertices and set *B* will contain the
remainder. *B*'s separable partitioning creates (*n*-1)/(*m*-1)
subsets of *m*-1-cliques. Arbitrarily match each subset with a unique
member of *A* and join this member to all *m*-1-cliques in the
subset to form *m*-cliques. These cliques, when united with the cliques
forming the partitioning of *A*, are a solution to the
entire <*m*,*n*> partitioning problem. All edges within
*A* are represented, because we've included a partitioning of *A*.
All edges within *B* are represented because we've included a partitioning
of *B*. Lastly, all edges between *A* and *B* are represented,
because each member of *A* has been assigned to *m*-1-cliques
that have, as the union of their vertices, all of *B*, as is the
property of separable partitionings.

**Lemma 2:** The partitioning presented in the proof of
theorem 1 is separable.

Again, we will construct the subsets explicitly. In theorem 1, the partitioning
was to all affine subspaces of dimension 1. The subsets we search for here
are all quotient spaces of the linear subspaces of dimension 1.

Plainly, we will group together all *m*-cliques that share the same
*A*. (Or, equivalently, whose *A*s are scalar multiples of one
another. These must be pairwise disjoint, because the *m*-cliques in
each subset represent parallel lines in *U*, and parallel lines do not
intersect.

Armed with these new lemmas, we are now able to prove theorem 2. We will prove
this by induction over *l*. First, if *l*=1 then the claim
degenerate to the trivial <*m*,*m*> question, which
obviously has a partitioning.

Next, let us assume that we already have a partitioning for
<*m*,*n*'=(*p*^{k(l+1)}-1)/(*p*^{k}-1)>
and we want to create a solution for
<*m*,*n*=(*p*^{k(l+2)}-1)/(*p*^{k}-1)>.
Note that *n*-*n*'=*p*^{k(l+1)}, so the
<*m*,*n*-*n*'> partitioning problem has a separable
solution according to lemma 2. Using these two known partitionings, the
desired partitioning is given by lemma 1.

**Theorem 3:** If *n*=(3^{k}+1)2^{l}-1,
for naturals *k* and *l*, then the <3,*n*> clique
partitioning problem has a solution.

To do this, consider the following lemma:

**Lemma 3:** If <3,*x*> has a clique partitioning solution, then
so does <3,2*x*+1>.

The proof of this lemma is by use of lemma 1. In order to comply with the
conditions of lemma 1, we must be able to present a separable partitioning for
the <2,*x*+1> problem. Note that *x* must be odd (or else
<3,*x*> would not have had a solution, for the same reason as
<5,576>). We will show that <2,2*k*>
has a separable partitioning for any natural *k*, so necessarily also for
*k*=(*x*+1)/2. This is done by the following well-known algorithm:
Let the 2*k* elements be denoted by the numbers 0 through 2*k*-1.
for the *i*'th subset, choose all pairs *a* and *b* satisfying
*a*+*b* = i (mod 2*k*-1) with both *a* and *b*
smaller than 2*k*-1. This pairs all except *ik* (mod 2*k*-1)
and 2*k*-1, so these two are paired together as well. This can easily
be ascertained to be a valid separable partitioning.

The proof of the theorem is by induction on *l*, starting from the
solution for *n*=3^{k}, which was guaranteed by theorem
1, then stepping from *l* to *l*+1 by use of lemma 3.

For *m*=3 there are many "expansion laws" of the sort presented by lemma
3, that allow us to create new solutions from existing ones. In order to
prove the claim, here are two such laws that we will make use of:

**Lemma 4:** If <3,*a*> and <3,*b*> each has a
partitioning solution, then so does <3,(*a*-1)*b*+1>.

To prove this, let (*a*-1)*b* elements be the pairs
(*x*,*y*) with *x* in (mod *a*-1) and *y* in
(mod *b*). First, add the following two types of triangles (=3-cliques):

- {(
*u*,*y*),(*v*,*y*),(*w*,*y*)} if {*u*,*v*,*w*} is part of the solution for <3,*a*> and none of*u*,*v*,*w*equals*a*-1. - {(
*x*,*u*),(*y*,*v*),(*x*+*y*(mod*a*-1),*w*)} if*u*<*v*<*w*and {*u*,*v*,*w*} is part of the solution for <3,*b*>.

**Lemma 5:** If <3,*a*> and <3,*b*> each has a
partitioning solution, then so does <3,(*a*-1)(*b*-1)/2+1>.

Let (*a*-1)(*b*-1) elements be denoted by the triplets
(*u*,*v*,*w*) with *u* in (mod (*a*-1)/2),
*v* in (mod (*b*-1)/2) and *w* in {0,1}, and choose a
<3,*b*> partitioning for the numbers in (mod *b*) that
includes all triangles of the form {*x*,*x* xor 1,*b*-1}
for *x*<*b*-1. This
can be achieved with any partitioning simply by renaming the elements.
Also, let us define one additional element *z*.

Now, let us use the following three types of triangles:

- {(
*x*,*u*,*q*),(*y*,*v*,*r*),(*x*+*y*mod (*a*-1),*w*,*s*)} if*u*<*v*<*w*and {2*u*+*q*,2*v*+*r*,2*w*+*s*} is part of the chosen (mod*b*) solution, and none of the elements equals*b*-1. - {(
*u*,*y*,*q*),(*v*,*y*,*r*),(*w*,*y*,*s*)} if {2*u*+*q*,2*v*+*r*,2*w*+*s*} is part of the solution to <3,*a*> and none of the elements equals*a*-1. - {(
*u*,*y*,*q*),(*v*,*y*,*r*),*z*} if {2*u*+*q*,2*v*+*r*,*a*-1} is part of the solution to <3,*a*>.

With these two lemmas, it is possible to prove the main claim.
To do this, let us first note that the condition *n*=1 or 3 (mod 6)
is clearly a necessary one,
for the same reasons as those stated in the proof that showed that neither
<7,345> nor <5,576> has a partitioning solution.

Next, let us construct an explicit construction for all *n* of the form
6*k*+3.
Let us describe all elements by a pair (*x*,*y*), where
*x* in {0,1,2} and *y* in {0..2*n*}.
We will use two types of triangles:
{(0,*y*),(1,*y*), (2,*y*)}
and
{(*x*,*y*), (*x*,*z*),
(*x*+1 mod 3,(*y*+*z*)*(*n*+1) mod (2n+1))}
with *y*≠*z*.

It is easy to verify that together these two types of triangles cover every
edge of the clique exactly once.

The remaining problems are of the form <3,6*k*+1>.
We claim that all of these have partitionings. We will show this by proving
that no <3,*n*> partitioning problem of this
form can be the one with the lowest *n* that has no partitioning
solution. First, consider lemma 4
with *a*=6*l*+3 and *b*=3. This leads to solutions to
all *n* such that *n*=18*l*+7.
Reversing the roles of *a* and *b*, we get partitioning
solutions also to all *n*=12*l*+7.
Next, using the fact that the <3,13>
clique-partitioning problem has a solution (a fact that can be ascertained
by trial and error), and substituting *a*=6*l*+3, *b*=13 into
lemma 5, we get that all <3,*n*> problems with *n*
of type 36*l*+13 have partitioning solutions.

These, together, indicate that if there is a lowest number, *n*, of the
form *n*=6*k*+1, for which the <3,*n*>
clique-partitioning problem has no solution, it must be of the form
36*l*+1. However, if it is the lowest such number, then
<3,6*l*+1> has a partitioning solution,
meaning that we can substitute
*a*=6*l*+1, *b*=13 into lemma 5, proving that <3,*n*>
must have a partitioning, too, contradicting the assumption that a lowest
number, *n*, of the form *n*=6*k*+1, exits,
for which the <3,*n*> clique-partitioning problem has no solution.

Summing all conclusions, this proves the claim that the <3,*n*>
clique partitioning problem has a solution if and only if *n* is equal
(mod 6) to either 1 or 3.

Q.E.D.

If you're interested to read more about this type of construction, a slight generalization of the concept is known as a Steiner System. Steiner Systems, in turn, are special cases of Block Designs.