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

Takayuki Hibi, Aki Mori, Hidefumi Ohsugi

Let $G$ be a finite connected simple graph with $n$ vertices and $m$ edges. We show that, when $G$ is not bipartite, the number of $4$-cycles contained in $G$ is at most $\binom{m-…