Timeline for Degree conditions sufficient for Hall's theorem
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 21, 2014 at 12:42 | history | edited | Ron Teller | CC BY-SA 3.0 |
added 14 characters in body
|
| Feb 21, 2014 at 12:38 | comment | added | David Richerby | The Dirac, Ore and Bondy–Chvátal theorems give some degree conditions for Hamiltonicity. As you observed in an earlier version of the question, the existence of a Hamiltonian cycle implies a matching (at least, for graphs of even order). | |
| Feb 21, 2014 at 12:33 | history | edited | David Richerby | CC BY-SA 3.0 |
Shorter title.
|
| Feb 21, 2014 at 12:32 | history | edited | Ron Teller | CC BY-SA 3.0 |
deleted 496 characters in body; edited title
|
| Feb 21, 2014 at 0:41 | comment | added | D.W.♦ | ... Perhaps you are asking for a threshold $t$ (depending only upon $n$) such that, if every vertex has degree $\ge t$, then the graph will surely have a perfect matching. Is that it? If so, what have you tried? Have you tried constructing counterexamples? Have you tried building small graphs by hand that lack perfect matchings and where all vertices have large-ish degree? We expect you to make an effort on your own before posting here, and to show us what you've tried. | |
| Feb 19, 2014 at 19:36 | history | tweeted | twitter.com/#!/StackCompSci/status/436222772092891136 | ||
| Feb 19, 2014 at 9:14 | history | edited | Ron Teller | CC BY-SA 3.0 |
added 455 characters in body
|
| Feb 19, 2014 at 8:31 | answer | added | Suresh | timeline score: 2 | |
| Feb 19, 2014 at 7:49 | history | asked | Ron Teller | CC BY-SA 3.0 |