Timeline for Are all almost regular graphs obvious?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 29, 2014 at 20:56 | comment | added | Tony Huynh | @DouglasZare Got it, thanks! I was keeping the edge $v_1v_2$, which was not smart. | |
| May 29, 2014 at 20:12 | comment | added | Douglas Zare | @Tony Huynh: Add a disjoint $K_d$, then choose an edge $v_1v_2$ of $K_d$ and an edge $w_1w_2$ of the graph $G$. Then you have two opposite edges of the $4$-cycle $v_1v_2w_1w_2$. Replace these with the other two opposite edges $v_1w_1$ and $v_2w_2$. This replacement doesn't change the degrees but it makes the graph connected, and separates those two vertices of $G$. | |
| May 29, 2014 at 17:00 | comment | added | Tony Huynh | Can you say a bit more about how you string together the $K_d$ graphs along each edge? The construction I have in my mind creates two degree $d$ vertices for each $K_d$, and so it is no longer true that the degree $d$ vertices are an independent set. Of course, everything is fine for $d=3$. | |
| May 28, 2014 at 20:28 | comment | added | Douglas Zare | That should have been "stringing together $K_d$ graphs." | |
| May 28, 2014 at 15:12 | comment | added | Douglas Zare | @joro: You can choose to add more than one vertex to an edge of the original graph. | |
| May 28, 2014 at 14:07 | comment | added | joro | Why The number of vertices of degree 2 is odd? If the number of edges is even this appears false to me. | |
| May 28, 2014 at 13:09 | history | answered | Douglas Zare | CC BY-SA 3.0 |