# 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.

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.
• Very nice,it reminded me of the proof of the following problem: Prove a $2k$ regular graph is $2$-factorizable. Jun 21, 2015 at 9:20