Deje $G=(V,E)$ ser un grafo no dirigido. Estoy usando la convención habitual que $n=|V|, m=|E|$. Para $v \in V$, vamos a $deg(v)$ ser el grado del vértice $v$.
Estoy tratando de mostrar que si tenemos $m > \frac{n^{3/2}}{2}$, se deduce que el $G$ tiene un triángulo $C_3$ o un cuadrado $C_4$. He encontrado una manera clara y ordenada que casi funciona, pero no es lo suficientemente fuerte...
Esto es lo que he hecho hasta ahora:
Primero de todo (no relativos a la solución de un problema relacionado) es un buen ejemplo de la de Cauchy-Riemann de la desigualdad muestran que cada gráfico de $G$ con más de $n^2/4$ bordes contiene un triángulo $C_3$ (esta es la Repisa de la chimenea del teorema).
Ahora hice esto (básicamente puedo reproducir una prueba dada por Erdős):
Trato de mostrar si $G$ no tiene plaza de $C_4$,$m \leq \frac{n^{3/2}}{2}$. Podemos considerar el importe $k$ de subdiagramas de $G$ que se parecen a $K_{1,2}$ ("cherry"). Ciertamente, si nosotros (doble) contar con los, considerando un vértice en el centro de la cereza, obtenemos:
$$k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$
Ahora bien, si no permitimos que los cuadrados de un par de vértices $\{v,w\}$ pueden ser los extremos de sólo una cereza, de lo contrario tendríamos un ciclo, por lo tanto
$$\binom{n}{2} \geq k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$
Entonces, debido a la convexidad de $\binom{x}{2}$, y el de la Desigualdad de Jensen se puede concluir ahora que $m \leq \frac{1}{4} \cdot \left(\sqrt{n^2 (4 n-3)}+n\right) $. Lamentablemente después de todo el trabajo que veo que asymtotically esto es suficiente, pero el obligado quiero mostrar es todavía un gran estanquidad:
Yo estaría muy contento si alguien me pudiera dar una alternativa de la prueba de que me da los estrechos límites o tal vez mejorar lo que hice (yo no uso el hecho de que todavía el $G$ es también el triángulo).
