The number of $4$-cycles and the cyclomatic number of a finite simple graph

Takayuki Hibi, Aki Mori, Hidefumi Ohsugi

Published 2018-01-18Version 1

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}$.