{
  "id": "1801.06169",
  "version": "v1",
  "published": "2018-01-18T18:47:35.000Z",
  "updated": "2018-01-18T18:47:35.000Z",
  "title": "The number of $4$-cycles and the cyclomatic number of a finite simple graph",
  "authors": [
    "Takayuki Hibi",
    "Aki Mori",
    "Hidefumi Ohsugi"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a finite connected simple graph with $d$ vertices and $e$ edges. The cyclomatic number $e-d+1$ of $G$ is the dimension of the cycle space of $G$. Let $c_4(G)$ denote the number of $4$-cycles of $G$ and $k_4(G)$ that of $K_4$, the complete graph with $4$ vertices. Via certain techniques of commutative algebra, if follows that $c_4(G) - k_4(G) \\leq \\binom{e-d+1}{2}$ if $G$ has at least one odd cycle and that $c_4(G) \\leq \\binom{e-d+2}{2}$ if $G$ is bipartite. In the present paper, it will be proved that every finite connected simple graph $G$ with at least one odd cycle satisfies the inequality $c_4(G) \\leq \\binom{e-d+1}{2}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-18T18:47:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30"
    ],
    "keywords": [
      "finite simple graph",
      "cyclomatic number",
      "finite connected simple graph",
      "odd cycle satisfies",
      "complete graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}