{
  "id": "1801.07025",
  "version": "v1",
  "published": "2018-01-22T10:19:01.000Z",
  "updated": "2018-01-22T10:19:01.000Z",
  "title": "Spanning trees without adjacent vertices of degree 2",
  "authors": [
    "Kasper Szabo Lyngsie",
    "Martin Merker"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that for every natural number $k$ there exists a $k$-connected graph of which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number $d$ such that every graph of minimum degree at least $d$ contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-22T10:19:01.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "adjacent vertices",
      "minimum degree",
      "natural number",
      "spanning tree contains vertices",
      "hutchinson"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}