Prueba bipartita

Question

Sea $G$ sea un grafo de orden $5$ o más. Demostrar que a lo sumo uno de $G$ y " $G$ complemento" es bipartito.

Estoy perdido en cuanto a lo que hay que hacer. Sé que Un gráfico no trivial $G$ es bipartita si y sólo si $G$ no contiene ciclos impar.

Answer 1

Lo que necesita es el hecho de que, si $G$ es un gráfico de orden $n$ entonces $\chi(G)\chi(\overline G)\ge n$ . Para ver esto observe que, si $V=V(G)=V(\overline G)$ y si $f:V\to[h]$ es una coloración propia de $G$ y $g:V\to[k]$ es una coloración propia de $\overline G$ entonces $x\mapsto(f(x),g(x))$ es un mapa unívoco de $V$ a $[h]\times[k]$ .

Ahora bien, si $G$ es un gráfico de orden $n$ y si $G$ y $\overline G$ son grafos bipartitos, entonces $n\le\chi(G)\chi(\overline G)\le2\cdot2=4$ .

Answer 2

Permítame darle una pista hacia una solución mucho, mucho más elemental:

Pista: Basta con demostrar que si $G$ es bipartita, entonces $\bar{G}$ (el complemento de $G$ ) no es bipartita.

Para ello, supongamos que $V(G)=A\cup B$ es una bipartición de $G$ . Entonces en $E(G)$ no hay bordes en el interior $A$ , sin bordes en el interior $B$ y puede haber algunos bordes entre $A$ y $B$ .

Basándose en esto, ¿qué $E(\bar{G})$ ¿Qué aspecto tiene? Desde $G$ no contiene aristas en su interior $A$ y sin bordes en el interior $B$ debe darse el caso de que $\bar{G}$ contiene TODAS las aristas dentro de $A$ y CADA borde interior $B$ .

Por lo tanto, si $\bar{G}$ fueran bipartitos, no podría darse el caso de que dos vértices cualesquiera de $A$ o dos vértices cualesquiera de $B$ cayeron en la misma parte de la bipartición.

¿Puedes ver cómo terminarlo desde aquí, usando la suposición de que hay al menos 5 vértices distribuidos entre $A$ y $B$ ?

Answer 3

Lo que se necesita aquí es el teorema de Ramsey.

http://en.wikipedia.org/wiki/Ramsey_theorem

En particular, el teorema de Ramsey dice que todo grafo con 6 o más vértices o bien tiene una camarilla de tamaño tres, o bien su complemento tiene una camarilla de tamaño tres.

Answer 4

Supongamos que uno de ellos es bipartito. Entonces, al menos una de las partes tiene 3 o más vértices. Elijamos 3 de ellos y llamémoslos u, v, w. Como estos 3 vértices están en la misma parte, no tienen conexión. Por lo tanto, en el grafo complemento hay aristas uv, uw y vw. Ahora, u, v, w, u es un ciclo de longitud 3 y muestra que el grafo complemento no puede ser bipartito.