Category: Problems

A Curious Bound on the Complexity of Graphs With No 4-Cycles

Posted on November 5, 2021January 15, 2022 by Russell Schwartz

Let $G$ be a connected graph with $n$ vertices and $m$ edges. If $G$ does not contain a $4$ -cycle, then $m \le \frac{n}{4}\left(1 + \sqrt{4n - 3}\right)$ . . .

Category: Problems

A Curious Bound on the Complexity of Graphs With No 4-Cycles

Recent Posts

Categories

Recent Comments