The definition of graceful graph is wrong. Edges E_{i,j} should have unique values as well, i.e. {E_{i,j}} = {1, 2, ..., n}. Otherwise it's trivial to label every graph into a graceful graph.
Pretty cool. I would think there would either be an algorithm to label the vertices or an example of one that cannot be elegantly labelled, but I guess not.
I's pretty obvious that node n must be adjacent to node 0, since that's the only way to get edge n. And it's pretty obvious that if you have one labeling you can get another by replacing m with n-m, so all the edges keep the same labels. But that's about as far as I get.
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.
9 comments
[ 3.2 ms ] story [ 33.3 ms ] threadIn 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
[2] https://tspace.library.utoronto.ca/bitstream/1807/13623/1/MQ... page 13 in their numbering
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?