Q:

Partition graph into disjoint beams

Given an undirected graph such that each vertex has degree exactly $100$. A beam is a set of $10$ edges connected to the same vertex. Prove that the set of all edges can be partitioned into disjoint beams.
The total number of edges is $100n/2=50n$, where $n$ is the number of vertices. For the complete graph with $101$ nodes (which is the minimum possible number of nodes), it is already not clear how to do the partition. 

A:

Let $G$ be our 100-regular graph with $n$ vertices.
Note that we may assume that $G$ is connected (if not we just apply the procedure on each component).
Take $5n$ pots of paint, all different colors.
Put just enough paint in each pot to paint 10 edges.
Drop 5 pots at each vertex.
Now $G$ is an even graph, so it has an Eulerian circuit.
Pick any vertex as starting vertex and travel the circuit.
At each vertex you pick a color that is not yet exhausted and you paint
the edge along which you leave in that color.
At the end you have colored all edges.
You have left each vertex 50 times, so all paint is gone.
The beams clearly stand out, since they are all monochromatic.
Note that you can considerably generalize the problem statement without
changing the proof in an essential way.
In fact, it may be a nice exercise to try how far you can generalize.
I bet, your first attempt will be improvable.

