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 27, 2014 at 19:55 | comment | added | Felix Goldberg | Ah, good point about the multigraphs. But I really do want my regular graph to be simple in this instance. (Although I mind loops less). | |
| May 27, 2014 at 19:43 | comment | added | Zack Wolske | @Felix: Yes, you're right, the edges could already be there. This only works when you don't care if the regular graph is simple. | |
| May 27, 2014 at 19:41 | history | edited | Zack Wolske | CC BY-SA 3.0 |
added 488 characters in body
|
| May 27, 2014 at 18:43 | comment | added | Felix Goldberg | But there might be some edges between the even set already in place. In other words - the subgraph induced by the even set is not necessarily empty, how are we sure it has a perfect mathching? I am not saying I think it's wrong, but I don't see how pairing them up can be enough. | |
| May 27, 2014 at 17:45 | comment | added | Zack Wolske | @Felix: There are an even number of vertices, so you can pair them up and add an edge for each pair. Their degrees all increase by one, and the other set is unchanged, so you get a regular graph. | |
| May 27, 2014 at 17:20 | comment | added | Felix Goldberg | How do you prove the first claim? ("If the size of both sets is even, then you can add a matching to the set with lower degree to get a regular graph") I don't quite get it. | |
| May 27, 2014 at 16:32 | history | answered | Zack Wolske | CC BY-SA 3.0 |