Timeline for Completing subcubic trees to cubic graphs
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 10, 2022 at 7:45 | comment | added | domotorp | Yes, I think you're correct. | |
| Dec 10, 2022 at 6:23 | comment | added | Brendan McKay | I was wondering if the additional edges can be chosen to be a cycle. Clearly it is impossible if $T$ has vertices of degree 2, but otherwise I think the same proof works if at each step we judiciously choose between adding $ua,vb$ or $ub,va$. | |
| Dec 9, 2022 at 22:05 | comment | added | domotorp | Good points - I guess we can fix an edge that closes a cycle of length $g$ with $T$ (such an edge must exist), and never touch that later. | |
| Dec 9, 2022 at 21:57 | comment | added | bof | The procedure terminates with a graph whose girth is at least $g$ but how do you know the girth is exactly $g$? | |
| Dec 9, 2022 at 21:55 | comment | added | bof | When picking $ab\in E(C)$ you should state that $ab\notin E(T)$ which is of course possible. | |
| Dec 9, 2022 at 11:58 | history | answered | domotorp | CC BY-SA 4.0 |