4 ms·
A month ago [1] there was a post about the proof of Ringel’s conjecture, that a complete graph can be covered by certain trees. Sadly it was a non-constructive
by cschmidt 7y ago
A month ago [1] there was a post about the proof of Ringel’s conjecture, that a complete graph can be covered by certain trees. Sadly it was a non-constructive proof.
In a little googling of the Graceful Tree Conjecture, it turns out that Ringel's conjecture inspired the Graceful Tree Conjecture [2]
It was shown that the GTC implies Ringel's conjecture. Fun to see the connection in the last two math problems I dipped into.
[1] https://news.ycombinator.com/item?id=22373701 https://news.ycombinator.com/item?id=22373701
[2] https://tspace.library.utoronto.ca/bitstream/1807/13623/1/MQ53395.pdf https://tspace.library.utoronto.ca/bitstream/1807/13623/1/MQ... page 13 in their numbering
- sdenton4 7y agoI, uh, wasted a bit of time once on the Tree Packing conjecture of Gyarfas: https://arxiv.org/abs/1104.0642 https://arxiv.org/abs/1104.0642 In your left hand, place a complete graph, which has n-choose-2 edges. In your right hand, a collection of trees on 2, 3, 4, ..., n-1 vertices, which, by miraculous concidence, also has n-choose-2 edges. Q: Can you pack the trees into a complete graph with no overlapping edges?