Si $G$ es cualquier grafo triangular libre de n vértices que no contenga una copia de $D_d$ entonces $e(G) \leq n(d-1)$

Question

Revisando para un próximo examen de Teoría de Grafos me encontré con el problema anterior. Era la última parte de una pregunta sobre Teoría de Grafos Extremos, y en las partes anteriores, la pregunta cubría el Teorema de Erdos-Stone para el caso especial de $r=3$ y el Problema Zarankiewski para grafos bipartitos (teorema de Kovári-Sós-Turán).

Toma, $D_d$ es el único árbol con $2d$ vértices que contienen 2 vértices adyacentes con grado $d$ ( $D_d$ es la estrella doble)

Observé que en primer lugar $G$ estar libre de triángulos implica que no contiene una copia de $K_3(1)$ . El límite $e(G) \leq n(d-1)$ también es similar al límite de $z(n,t) \leq (t-1)^{1/t}n^{2-1/t}+(t-1)n$ para el problema de Zarankiewski (he demostrado el límite de $ex(2n, K_{t,t} \leq 2(t-1)^{1/t}n^{2-1/t} + 2(t-1)n$ en una parte anterior). Además $z(n,t)$ es un límite relativo al número extremo de grafos bipartitos, y puesto que $D_d$ es bipartita, parece que el límite mostrado anteriormente se utilizará aquí. Todo lo cual apunta sospechosamente a las partes anteriores.

Sin embargo, a pesar de ello, no veo la manera de resolver este problema.

Answer 1

Supongamos que $G$ es un grafo sin triángulos con $n$ vértices y al menos $n(d-1)$ bordes.

Si hay un vértice $v$ de grado como máximo $d-1$ entonces $G-v$ es un grafo sin triángulos con $n-1$ vértices y al menos $(n-1)(d-1)$ bordes. Repitiendo esto durante el mayor tiempo posible, llegamos a un grafo sin triángulos con $k$ vértices, al menos $k(d-1)$ aristas, y grado mínimo $d$ .

Ahora toma cualquier borde $vw$ junto con $d-1$ más vecinos de $v$ y $d-1$ más vecinos de $w$ ; como el grafo no tiene triángulos, ninguno de esos vecinos es común entre $v$ y $w$ así que tenemos una estrella doble.