{
  "id": "1408.5289",
  "version": "v1",
  "published": "2014-08-22T13:13:10.000Z",
  "updated": "2014-08-22T13:13:10.000Z",
  "title": "Graphs without proper subgraphs of minimum degree 3 and short cycles",
  "authors": [
    "Lothar Narins",
    "Alexey Pokrovskiy",
    "Tibor Szabó"
  ],
  "comment": "22 pages, 14 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study graphs on $n$ vertices which have $2n-2$ edges and no proper induced subgraphs of minimum degree $3$. Erd\\H{o}s, Faudree, Gy\\'arf\\'as, and Schelp conjectured that such graphs always have cycles of lengths $3,4,5,\\dots, C(n)$ for some function $C(n)$ tending to infinity. We disprove this conjecture, resolve a related problem about leaf-to-leaf path lengths in trees, and characterize graphs with $n$ vertices and $2n-2$ edges, containing no proper subgraph of minimum degree $3$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-08-22T13:13:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38",
      "05C05",
      "05C75"
    ],
    "keywords": [
      "minimum degree",
      "proper subgraph",
      "short cycles",
      "leaf-to-leaf path lengths",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1408.5289N"
    }
  }
}