Pairing students with all other students There are $n$ students in a class, where $n$ is even. Each day, the teacher assigns them into pairs, so that no one is unmatched, and also no two students are paired together twice. Can the teacher do this until all students have been paired with all other students?
For example, for $n=4$ the teacher can do it, by pairing $(1,2),(3,4)$ on the first day, $(1,3),(2,4)$ on the second day, and $(1,4),(2,3)$ on the third day. For $n=6$ this is also possible.
 A: This problem is the same as taking the complete graph in $n$ vertices $K_n$ and coloring the edges with $n-1$ colors so that no vertex has two edges of the same color.
If $n$ is odd it is not possible because the graph with only the edges of one color would be regular of degree $1$, so it would then have an odd sum of degrees. Contradicting the handshaking lemma.
If $n$ is odd what you can do is color the edges of $K_n$ with $n$ colors so that every vertex has edges of all the colors except for one. And the missing color is different for each one. The way to do this is called the tortilla algorithm in my country. Take a regular $n$-gon and for each edge use a color to paint that edge and all of the diagonals parallel to that edge, therefore we use a color for each class of parallel diagonals. Suppose we color an edge purple. Then the only vertex missing a purple edge is the one that is opposite to that edge.
Using the tortilla algorithm we can color the edges of $K_{2n}$ with $2n-1$ colors so that every verex has exactly one edge of each color (when $n$ is odd). To do this place the vertices in two regular $n$-gons and first color the edges of those $n$-gons using the first $n$-colors. Label the vertices $1,2,3,4,\dots n$ in each of the $n$-gons So that vertex $j$ does not have an edge of color $j$. After that color the edge between vertex $j$ in the first $n$-gon and vertex $j$ in the second $n$-gon with color $j$. So that now each vertex has one vertex of each of the first $n$ colors. We need to use the final $n-1$ colors.But this is possible because the edges that remain to be colored form a regular bipartite graph, therefore it's edge set can be seen as a disjoint union of matchings. Take one of the remaining colors for each of the matchings and you are done.
Therefore we have solved the case $2n$ with $n$ odd. to solve the case $2n$ with $n$ even proceed by induction on the largest power of $2$ dividing $n$. So suppose we have proven it for $n$. To prove it for $2n$ just take two sets of $n$ vertices and label each of them $1,2,3,4,\dots n$ and again $1,2,3\dots 2n$. Then  use the induction hypothesis to color the edges between the vertices of the two sets of $n$ vertices so that each of them  has one edge of each of the first $n-1$ colors. For the remaining edges we need to use the final $n$ colors. to do this label the other $n$ colors $1,2,3\dots n$ and color the edge between vertex $m$ in the first set and $k$ in the second set with the color congruent to $m+k\bmod n$. 
Therefore it is possible if and only if $n$ is even.
A: You can Show the proposition by induction. Start with $n=2$. Then consider arbitrary even number $n$ and assume that the proposition is true for this even number. Now you have to Show that the proposition is also true for $n+2$ (where you have involved only 2 more students). You have the Pairing $(x_1,y_1),(x_2,y_2),...,(n+1,n+2)$ where $x_i,y_i$ for natural number $i$ are all the students that are paired in the case with $n$ students. Other combinations arise from all possible Pairings one of the 2 "new" students with the "old" students.
