Theorem 1: If m=pk and n=ml 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=pk and
n=ml 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=Ax+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
Ax+B=Ax'+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=pk+1 and n=(pk(l+1)-1)/(pk-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 (pk)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 (pk(l+1)-1)/(pk-1) different elements and any line in it (a 2D linear subspace in the original vector space) has (p2k-1)/(pk-1), or simply pk+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 As 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'=(pk(l+1)-1)/(pk-1)>
and we want to create a solution for
<m,n=(pk(l+2)-1)/(pk-1)>.
Note that n-n'=pk(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=(3k+1)2l-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,2x+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,2k> 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 2k elements be denoted by the numbers 0 through 2k-1. for the i'th subset, choose all pairs a and b satisfying a+b = i (mod 2k-1) with both a and b smaller than 2k-1. This pairs all except ik (mod 2k-1) and 2k-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=3k, 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):
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:
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
6k+3.
Let us describe all elements by a pair (x,y), where
x in {0,1,2} and y in {0..2n}.
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,6k+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=6l+3 and b=3. This leads to solutions to
all n such that n=18l+7.
Reversing the roles of a and b, we get partitioning
solutions also to all n=12l+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=6l+3, b=13 into
lemma 5, we get that all <3,n> problems with n
of type 36l+13 have partitioning solutions.
These, together, indicate that if there is a lowest number, n, of the
form n=6k+1, for which the <3,n>
clique-partitioning problem has no solution, it must be of the form
36l+1. However, if it is the lowest such number, then
<3,6l+1> has a partitioning solution,
meaning that we can substitute
a=6l+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=6k+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.