> Consider: g = graph({1:[2,3,4,5],2:[3,5],4:[3,5]}).
Hahahahhahaaha ! Dead right :-)
And the code works anyway because the tree it returns actually is *NOT* a
BFS tree :-)
sage: g.lex_BFS(tree = True)[1].edges()
[(2, 1, None), (3, 2, None), (4, 5, None), (5, 2, None)]
Two (obvious) black patches in my previous proof :
* It totally ignores the edges between classes of vertices with the same
distance to the source -- precisely what your counter-example destroys.
* without considering "the last neighbor of v discovered before v itself",
its process does not ensure that the neighborhood of a removed vertex is
indeed simplicial. Very bad indeed :-)
For a time I thought I would be able to patch my proof, but in the end I
don't get how this recognition algorithm works... Which is a pity because I
am sure I had found a clear explanation in a paper when I implemented all
that stuff. What I need right now is some sleep though. Sounds like this
will really require a patch :-)
Thank you for your perseverance ! At the least I enjoyed the time thinking
of this algorithm again and (re ?)-learned a few nice tricks ;-)
Good niiiiiiiiight !
Nathann
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
