Let's assume $G$ is a simple graph, having $n$ vertices and $m$ edges. What I want to prove is that if $$m > \frac12 n \sqrt{n+1}$$ then $G$ includes at least a cycle of length 3 or 4 (triangle or square).

Note: What I've tried is to make proof by contradiction, assuming there is a vertex $v$ being included in no square or triangle, but have not resulted in anything useful yet.

  • $\begingroup$ Is there some restriction on $n$? For example, if $n=3$ we have $m \gt \frac{1}{2} 3 \sqrt{3+1}=\frac{1}{2} 3 \times 2 =3$. However, if you have a simple graph with 3 vertices and 4 edges you will have a cycle of length 3 plus a leftover edge that doesn't have two associated vertices. Just wanted to point that out - perhaps the definition of the problem needs to be double-checked. I hope this helps. $\endgroup$ – ad2004 Jun 30 at 2:36
  • 3
    $\begingroup$ @ad2004 The problem given in the question is the exact problem I’ve encountered and there is no additional condition. About your example, we can’t have a simple graph with 3 vertices have more than 3 edges, so I personally think because the question has stated “simple graph”, this example would not be a counterexample for the problem. $\endgroup$ – Jigsaw Jun 30 at 2:44
  • $\begingroup$ Have you tried looking on the dual graph? $\endgroup$ – NeitherNor Jun 30 at 6:43
  • $\begingroup$ @NeitherNor What if $G$ is not a planar graph? $\endgroup$ – Angela Pretorius Jun 30 at 6:45
  • $\begingroup$ Theorem 4.1 here gives the bound $m>\frac{1}2n(\sqrt{n}+1)$. It's not as tight as the OP's bound. arxiv.org/abs/1306.5167v2 $\endgroup$ – Angela Pretorius Jun 30 at 6:48

In fact, an even tighter bound holds:

A graph of girth at least five with $n$ vertices has at most $\frac{1}2n\sqrt{n-1}$ edges.

The following proof is taken from page 8, theorem 2.2 in the following paper:

Extremal graphs of girth five, Lazebnik et al (1993) http://www.math.udel.edu/~lazebnik/papers/techrep.pdf

Preliminary definitions:

-The girth of a graph is the length of the shortest cycle that it contains.

-The diameter of a graph is the maximum distance between any two vertices.

-Call a graph $G$ extremal if it has girth at least five and there does not exist any other graph of girth at least five with the same number of vertices and strictly fewer edges.

Lemma 1: Every extremal graph has diameter at most three.

Proof of lemma 1: Let $x,y$ be vertices of distance at least four in an extremal graph. Then adding the edge $xy$ to the graph would produce another graph of girth five.

Let $D_i$ be the number of unordered pairs of vertices whose distance is at most $i$ and $d(x)$ be the degree of the vertex $x$.

Lemma 2: In any girth of girth at least five, $D_2=\sum_{x\in V(G)}\binom{d(x)}2$

Proof of lemma 2: Let $y,z$ be one of the $\binom{d(x)}2$ pairs of vertices adjacent to $x$. If $y$ were adjacent to $z$, we would have a triangle. If $y,z$ were also adjacent to some $x'$ then we would have a four-cycle.

Main statement: Any extremal graph has at most $e=\frac{1}2n\sqrt{n-1}$ edges.

Proof of main statement:

From the lemmas, $\binom{n}2=D_1+D_2+D_3=e+\sum_{x\in V(G)}\binom{d(x)}2+D_3$.

Let $\overline{d}$ be the average degree of the graph and $\sigma^2=\sum_{x\in V(G)}(d(x)-\overline{d})^2$. Obviously $2e=\sum_{x\in V(G)}d(x)$ and $\overline{d}=2e/n$.

Then $\sum d(x)^2=\sigma^2-\sum \overline{d}^2-2\sum d\overline{d}=\sigma^2+4e^2/n$.

So $\binom{n}2=\sigma^2/2+2e^2/n+D_3$. If we take $\sigma^2=D_3=0$ then we get the desired upper bound on $e$.

| cite | improve this answer | |

I'll present perhaps a "friendlier-looking" (though that is a matter of personal opinion) proof of the same statement that Angela pursues in their answer above; it isn't better, just a different presentation that you may prefer. Be warned, however -- you will have to fill-in some blanks for yourself along the way.

Proposition. Let $G$ be a graph of order $n$ and size $m$. If $m > \frac{1}{2}n\sqrt{n-1}$, $G$ has girth at most $4$.

Proof. Consider the number $\sum_{v \in V(G)}\binom{deg(v)}{2}$; it counts the number of triples of vertices $v_1, v_2, v_3$ such that $v_1$ is a neighbor of both $v_2$ and $v_3$ (why? Reading Angela's proof of lemma 2 will help). Under the assumption that $G$ hasn't any $3$- or $4$-cycles, we can obtain the inequality $$\sum_{v \in V(G)}\binom{deg(v)}{2} \leq \binom{n}{2} - m$$ quite easily (any pair of adjacent vertices has no common neighbor (else a triangle) and no pair of nonadjacent vertices has $\geq 2$ common neighbors (else a $C_4$)). If you prefer it in words, we are "bounding the number of common neighbors of a given pair of vertices."
To obtain the sharpest bound possible, we wish to minimize the number $\sum_{v \in V(G)}\binom{deg(v)}{2}$. As always, we're working with the Handshaking Lemma's constraint of $\sum_{v \in V(G)}deg(v) = 2m$, and we can easily observe that $\sum_{v \in V(G)}\binom{deg(v)}{2}$ is minimized by taking $deg(v) = 2m/n$ for each $v$ (sample some alternative ways to distribute the degrees to convince yourself of this fact). From here, it's all algebra; we have the inequality $$n(\frac{m}{n})(\frac{2m}{n-1}) \leq \frac{n(n-1)}{2} - m$$ which eventually simplifies to $$m \leq \frac{1}{2}n\sqrt{n-1},$$ the desired contradiction. $\square$

Remark. Of course, this proves something stronger than your desired statement. I couldn't think of an inequality which works out to be exactly what's given in your question, but it's quite possible that there is a more elementary method which proves your weaker result (which would probably be the method which the person who wrote the question had in mind).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.