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

Abstract

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 $\left(\genfrac{}{}{0ex}{}{m-n+1}{2}\right)$. We further provide a short combinatorial proof of the bound $\left(\genfrac{}{}{0ex}{}{m-n+2}{2}\right)$ which holds for bipartite graphs.

arXiv comment19 pages, writings are improved