Timeline for Relationship between triangle free graphs and their minimum degree
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 6, 2014 at 9:03 | history | suggested | Sergiy Kozerenko | CC BY-SA 3.0 |
minor TeX changes
|
| Jul 6, 2014 at 9:01 | review | Suggested edits | |||
| S Jul 6, 2014 at 9:03 | |||||
| Sep 12, 2013 at 13:23 | review | Suggested edits | |||
| Sep 12, 2013 at 13:29 | |||||
| Jul 19, 2013 at 3:27 | vote | accept | Anand | ||
| Jul 17, 2013 at 6:55 | comment | added | Aaron Meyerowitz | Very nice. So in a graph with $n$ vertices and minimum degree $\delta$ every edge is in at least $2\delta-n$ triangles. It is possible to have $n=2\delta$ and no triangles but if $n \le 2\delta-1$ then every edge is in a triangle so there are lots of triangles. | |
| Jul 17, 2013 at 6:49 | comment | added | The Masked Avenger | Indeed, a couning argument might show something mildly stronger: a non bipartite graph which is triangle free has either a minimum degree less than 2n/5, or the graph is 2n/5-regular. This could well be part of an undergraduate graph theory course. | |
| Jul 17, 2013 at 5:37 | comment | added | The Masked Avenger | Given the elementary nature of the analysis in this answer, I would like to see the corollary mentioned in the question and how it is more interesting than the supposedly weaker alternative. | |
| Jul 17, 2013 at 5:32 | history | answered | The Masked Avenger | CC BY-SA 3.0 |