4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice,it reminded me of the proof of the following problem: Prove a $2k$ regular graph is $2$-factorizable. $\endgroup$ – Jorge Fernández Hidalgo Jun 21 '15 at 9:20
  • $\begingroup$ Interesting. The proof I know of your statement uses a graph transformation and apart from using an Eulerian circuit it is rather different. $\endgroup$ – Leen Droogendijk Jun 21 '15 at 9:37
  • $\begingroup$ Well, I guess it's different, but it uses the Eulerian cycle and it uses the notion of going in vs coming out of a vertex which I think is key. $\endgroup$ – Jorge Fernández Hidalgo Jun 21 '15 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.