Te estoy pidiendo ayuda con este problema
"Deje que$G$ sea un gráfico sin triángulos con$\delta > \frac{2n}{5}$. Demuestre que$G$ es bipartito".
Todos los libros que leo dicen que es obvio, pero no puedo ver por qué. Estoy un poco atascado.
Respuestas
¿Demasiados anuncios?
justartem
Puntos
13
Supongamos por contradicción que $G$ no es bipartito, vamos a $C$ ser un extraño ciclo de longitud mínima $l$.
Cada vértice fuera de $C$ es adyacente a la mayoría de las $2$ vértices de $C$. Si un vértice es adyacente a al menos tres vértices podemos encontrar un ciclo impar menor que $C$, esto sería una contradicción (tratar de demostrar esto, es un buen ejercicio).
Entonces, ¿cuál es el máximo de la suma de los grados de los vértices en el $C$ posible? es menor o igual a$(n-l)\cdot2+2\cdot l=2n$, ¿por qué? Ya existen en la mayoría de las $(n-l)\cdot 2$ bordes de salir de la $C$ e hay $l$ bordes entre los vértices de $C$ (si hay una arista entre los vértices consecutivos del ciclo, esto implicaría un menor impar ciclo) la suma es en la mayoría de las $2(n-l)+2l$ (los bordes entre los bordes de $C$ agregar $2$ a la suma de grados). Por lo tanto, la suma de los grados de los vértices del ciclo es en la mayoría de las $2n$. esto implica que hay un vértice con grado de $\frac{2n}{5}$ o menos(ya que el número de vértices en el ciclo es $5$ o más).
En busca de una contradicción, supongamos $G$ no es bipartito. A continuación, $G$ tiene un ciclo de longitud impar; deje $v_0, v_1, \ldots ,v_{k}$ ser los vértices del ciclo, en su respectivo orden. Como algunos de notación, vamos a $N(v)$ denota el conjunto de los vecinos de $v$. Entonces si $|i - j| >2$ (cuando se toma $\mod(k)$), entonces debemos tener $N(v_i) \cap N(v_j) = \emptyset$ por el minimality de nuestro ciclo. Por otra parte, desde la $G$ es triángulo libre, si $u$ e $v$ son adyacentes, entonces $N(u) \cap N(v) = \emptyset$ así. Si $k \geq 7$ entonces tenemos que $3$ e $4$ están a una distancia de más de $2$, lejos de la $0$ al ve $\mod(k)$. Por lo tanto, tenemos que $N(v_0) \cap N(v_3) \cap N(v_4)$. Sin embargo, esto es imposible, ya $N(v_i) > 2n/5$, por lo que tendríamos $|N(v_0) \cup N(v_3) \cup N(v_4)| > 6n/5$. Por lo tanto, tenemos que $k < 7$. Desde $k$ claramente no puede ser $3$ ($G$ es triángulo gratis), debemos tener $k = 5$.
La visualización de los subíndices $\mod(5)$, tenemos que $N(v_i) \cap N(v_{i+1}) = \emptyset$ e $N(v_{i-1}) \cap N(v_i) = \emptyset$. Esto implica entonces que el $|N(v_{i-1}) \cap N(v_{i+1})| > n/5$. Definir $A_i = N(v_{i-1}) \cap N(v_{i+1})$ por cada $i \in \{0,1,\ldots,4\}$. A continuación, tomamos nota de que $A_i \cap A_j = \emptyset$ para $i \neq j$. Esto, sin embargo, es una contradicción: el $A_i$ son pares de conjuntos disjuntos, cada uno con cardinalidad $> n/5$. Por lo tanto, $G$ no es bipartito.
