$K_{2^p+1}$ no es una unión de$p$ gráficos bipartitos

Question

Lo que quiero mostrar es que entre$2^p+1$% de puntos en el plano hay tres que determinan un ángulo de tamaño de al menos$\pi(1-1/p)$.

Me dijeron que tengo que empezar mostrando por$n=2^p$ que el gráfico$K_{n+1}$ no es la unión de$p$ gráficos bipartitos, pero$K_n$ es.

No tengo idea de cómo probar esto. Mis primeras ideas fueron la inducción o la prueba por contradicción, pero ninguna fue útil. También podría tener algo que ver con el hecho de que cada grpah bipartita es 2-coloreable.

Answer 1

Parece que el siguiente.

La proposición. El gráfico de $K_{2^p+1}$ no es una unión de $p$ grafos bipartitos.

Prueba. Asumir lo contrario: existe una familia de $\{\Gamma_i:i\in [p]=\{1,\dots,p\}\}$ de bipartito subdiagramas de un gráfico de $\Gamma=K_{2^p+1}$ tal que $\Gamma$ es la unión de la familia,$\{\Gamma_i\}$. Deje $(V_i ,W_i)$ ser el desdoblamiento de los vértices de la gráfica de $\Gamma_i$. Deje $\Delta_i$ ser un completo gráfico bipartito con el desdoblamiento $V_i\cup (V\setminus V_i)$ de los vértices, donde $V$ es el conjunto de todos los vértices de la gráfica de $\Gamma$. A continuación, $\Gamma_i$ es un subgrafo de $\Delta_i$ $\Delta_i$ es un subgrafo de $\Gamma$. A continuación, $\Gamma$ es la unión de la familia,$\{\Delta_i\}$. Ahora definir un mapa de $f:V\to\{0,1\}^p$ como sigue. Deje $v$ ser un vértice de la gráfica de $\Gamma$. Para cada índice $i$ puesto $f_i(v)=0$ si $v\in V_i$$f_i(v)=1$, de lo contrario. Poner $f=\prod_{i\in [p]} f$ $f(v)=(f_1(v),\dots, f_p(v)).$ Desde $|V|=2^p+1>2^p=|\{0,1\}^p |$, existen diferentes vértices $v_1,v_2\in V$ tal que $f(v_1)=f(v_2)$. Pero, a continuación, el borde entre el $v_1$ $v_2$ no pertenece a cada uno de los gráficos de $\Delta_i$, una contradicción.