Sea $T$ sea un grafo sin triángulos en $n$ vértices con grado mínimo $\delta$ (que puede ser $0$ ). ¿Cómo se demuestra que $n >2\delta -1$ ? Parece ser cierto para grafos bipartitos, pero no veo cómo demostrarlo para grafos libres de triángulos en general. La motivación detrás de esta pregunta es que si esto se resuelve, tendré un corolario mucho más interesante para obtener de él. Muchas gracias.
Respuestas
¿Demasiados anuncios?
Además de la bibliografía mencionada en las otras respuestas, se pueden probar algunas argumentos basados en el recuento.
Sea $u$ y $v$ sean dos de $n$ vértices en un grafo sin triángulos, y suponer además que son distintos y están conectados por una arista, con grados $c$ y $d$ y $c$ como máximo $d$ . Entonces sus vecindades son disjuntas, por lo que $c - 1 + d - 1$ es como máximo $n-2$ , dando $2\delta \leq n$ .
Podría ser divertido recrear el $2n/5$ resultado: he aquí un comienzo. Tome un ciclo impar de un grafo no bipartito con longitud de ciclo mínima. Si el ciclo es $7$ o mayor, demuestre que tres vértices producirán un triángulo, un ciclo de longitud impar más corto, o un grado como máximo $2n/5$ . Intente un análisis similar con un $5$ -ciclo. ¡Que aproveche!
anjanb
Puntos
5579
Si puedes demostrarlo para grafos bipartitos, esto se deduce en general, por el siguiente teorema de la referencia de abajo: cualquier grafo libre de triángulos de grado min mayor que $2n/5$ es bipartita.
@ AUTHOR = {Andr{{'a}sfai, B. and Erd{{ \H {o}s, P. y S{'o}s, V. T.}, TITLE = {Sobre la conexión entre cromati grado mínimo JOURNAL = {Matemáticas Discretas.}, FJOURNAL = {Matemáticas Discretas}, VOLUME = {8}, AÑO = {1974}, PAGES = {205--218}, ISSN = {0012-365X}, MRCLASS = {05C15}, MRNUMBER = {0340075 (49 #4831)}, MRREVIEWER = {D. J. Kleitman}, }
Matthew
Puntos
111
Esto se deduce de resultados familiares una vez que todo está desenredado. Supongamos que tenemos un grafo libre de triángulos con $n=2m$ o $n=2m+1$ vértices. Entonces $\delta \le m$ así que $2 \delta \le n.$ Esto se desprende de los comentarios que figuran a continuación.
Usted desea mostrar:
En un grafo sin triángulos $2\delta-1 \lt n.$
Desde $\delta$ es un número entero, es lo mismo que $2\delta \ \le n$ es decir $\delta \le \frac{n}{2}.$ Basta con demostrar $\delta' \le \frac{n}{2}$ donde $\delta' = \frac{2|E|}{n} $ es el grado medio, ya que claramente $\delta \le \delta'.$
Teorema de Turans (prueba en el enlace) tiene como caso especial el teorema de Mantel:
Un grafo libre de triángulos en $n$ vértices tiene como máximo $\big\lfloor\frac{n^2}{4}\big\rfloor$ bordes.
Así pues, los casos para un grafo sin triángulos son
- $n$ incluso , $|E| \le \frac{n^2}{4}$ y $\delta'=\frac{2|E|}{n} \le \frac{n}{2}$
junto con
- $n$ impar , $|E| \le \frac{n^2-1}{4}$ y $\delta'=\frac{2|E|}{n} \le \frac{n}{2}-\frac{1}{2n}.$
