text: # Small cycles in an undirected graph
  
  Let $G=(V,E)$ be an undirected graph. I am using the usual convention that $n=|V|, m=|E|$. For $v \in V$, let $deg(v)$ be the degree of the vertex $v$.
  
  I am trying to show that if we have $m > \frac{n^{3/2}}{2}$, it follows that $G$ has either a triangle $C_3$ or a square $C_4$. I found a neat way that almost works, but it is not tight enough...
  
  Here is what I have done so far:
  
  First of all (not concerning the solution but a related problem) it is a neat example of the Cauchy-Riemann inequality to show that every graph $G$ with more than $n^2/4$ edges contains a triangle $C_3$ (this is Mantel's theorem).
  
  Now I did this (basically I reproduce a proof given by Erdős):
  
  I try to show if $G$ has no square $C_4$, then $m \leq \frac{n^{3/2}}{2}$. We can consider the amount $k$ of subgraphs of $G$ that look like $K_{1,2}$ (a "cherry"). Certainly if we (double) count those, considering a vertice in the center of the cherry, we get:
  
  $$k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$
  
  Now if we don't allow squares a pair of vertices $\{v,w\}$ can be endpoints of only one cherry, otherwise we would have a cycle, therefore
  
  $$\binom{n}{2} \geq k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$
  
  Then due to convexity of $\binom{x}{2}$ and the Jensen Inequality one might conclude now that $m \leq \frac{1}{4} \cdot \left(\sqrt{n^2 (4 n-3)}+n\right)$. Sadly after all the work I see that asymtotically this is enough but the bound I want to show is still a big tighter:
  
  I would be very glad if someone could give me an alternate proof that gives me the tight bounds or maybe refine what I did (I did not use the fact yet that $G$ is also triangle-free).
  
  -
explanation: The text extract is a detailed mathematical discussion about the properties of an undirected graph \( G \). The author is trying to prove that if the number of edges \( m \) in the graph is greater than \( \frac{n^{3/2}}{2} \), then the graph must contain either a triangle \( C_3 \) or a square \( C_4 \). The author presents a proof that shows if the graph has no square \( C_4 \), then \( m \leq \frac{n^{3/2}}{2} \), but the bound is not as tight as desired. The author is seeking an alternate proof or a refinement of the current proof to achieve the desired bound.
  
  The text contains a question at the end, asking for an alternate proof or a refinement of the current proof to achieve the tighter bound.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # Small cycles in an undirected graph
  
  Let $G=(V,E)$ be an undirected graph. I am using the usual convention that $n=|V|, m=|E|$. For $v \in V$, let $deg(v)$ be the degree of the vertex $v$.
  
  I am trying to show that if we have $m > \frac{n^{3/2}}{2}$, it follows that $G$ has either a triangle $C_3$ or a square $C_4$. I found a neat way that almost works, but it is not tight enough...
  
  Here is what I have done so far:
  
  First of all (not concerning the solution but a related problem) it is a neat example of the Cauchy-Riemann inequality to show that every graph $G$ with more than $n^2/4$ edges contains a triangle $C_3$ (this is Mantel's theorem).
  
  Now I did this (basically I reproduce a proof given by Erdős):
  
  I try to show if $G$ has no square $C_4$, then $m \leq \frac{n^{3/2}}{2}$. We can consider the amount $k$ of subgraphs of $G$ that look like $K_{1,2}$ (a "cherry"). Certainly if we (double) count those, considering a vertice in the center of the cherry, we get:
  
  $$k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$
  
  Now if we don't allow squares a pair of vertices $\{v,w\}$ can be endpoints of only one cherry, otherwise we would have a cycle, therefore
  
  $$\binom{n}{2} \geq k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$
  
  Then due to convexity of $\binom{x}{2}$ and the Jensen Inequality one might conclude now that $m \leq \frac{1}{4} \cdot \left(\sqrt{n^2 (4 n-3)}+n\right)$. Sadly after all the work I see that asymtotically this is enough but the bound I want to show is still a big tighter:
  
  I would be very glad if someone could give me an alternate proof that gives me the tight bounds or maybe refine what I did (I did not use the fact yet that $G$ is also triangle-free).
  
  -
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The text extract is a detailed mathematical discussion about the properties of an undirected graph \( G \). The author is trying to prove that if the number of edges \( m \) in the graph is greater than \( \frac{n^{3/2}}{2} \), then the graph must contain either a triangle \( C_3 \) or a square \( C_4 \). The author presents a proof that shows if the graph has no square \( C_4 \), then \( m \leq \frac{n^{3/2}}{2} \), but the bound is not as tight as desired. The author is seeking an alternate proof or a refinement of the current proof to achieve the desired bound.
  
  The text contains a question at the end, asking for an alternate proof or a refinement of the current proof to achieve the tighter bound.
  
  Label: question