Timeline for Subset of edges of graph touching all vertices such that all paths consist of at most two edges
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 16, 2012 at 18:33 | comment | added | Gerhard Paseman | And to respond to Fred's earlier comment, my procedure would be problematic if there were a mapping to omega + 1, but since I posit not, his central vertex gets processed soon enough, and does not apply as a counterexample. I need the explicit bijection (or morally sufficient substitute) to avoid such problems. Gerhard "And Then There Were None" Paseman, 2012.08.16 | |
| Aug 16, 2012 at 18:29 | comment | added | Gerhard Paseman | Indeed, morning plus caffeine show my transfinite extension to be flawed. I think Fred has the right take on it, as it seems ugly and problematic to take an approach like mine or like Aaron's initial attempt. Gerhard "Ask Me About System Design" Paseman, 2012.08.16 | |
| Aug 16, 2012 at 8:37 | comment | added | Gerhard Paseman | Sorry Fred. I see your comment but my eyes are blurry. Will read it sooon. Gerhard " Really Must Go To Sleep" Paseman, 2012.08.16 | |
| Aug 16, 2012 at 8:36 | comment | added | Gerhard Paseman | Indeed, assuming Choice, there is a transfinite version of the above. I suspect being able to do so is equivalent to AC. Theidea is to add back edges to lower labeled pint in a small way, and remove an edge afterwards in case there is a long path. But I need to sleep. Gerhard "Perhaps Clarity Comes With Morning" Paseman, 2012.08.16 | |
| Aug 16, 2012 at 8:30 | comment | added | Fred.Fred | Thanks for input! If I understood your algorithm correctly, I think it could produce a vertex of degree 0 even in the countably infinite case. Say I have a star with $\omega$ rays consisting of two edges and the algorithm processes the "middle" vertices of the rays first. Then I end up with the middle vertex of the star disconnected. For the correcting step, I think that similar star graph with rays of length 3 and suitable numbering of vertices would get lead to situation, where you cannot add any edge connecting the center back without creating a path of length 3. | |
| Aug 15, 2012 at 20:34 | comment | added | Gerhard Paseman | One thing to watch for in the limit is that a vertex may get degree 0. When that happens, you can add an edge back, but you have to keep track and make sure your path condition is not locally undone. Gerhard "Takes Some And Leaves Some" Paseman, 2012.08.15 | |
| Aug 15, 2012 at 20:29 | history | answered | Gerhard Paseman | CC BY-SA 3.0 |