Conjunto mínimo de aristas.

Question

No se le da el grafo completo $K_{n}$.

Deje $A(n,k)=$mínima (en relación a su tamaño) subconjunto de los bordes de las $K_{n}$ tales todos los $k$-camarilla tiene al menos un borde en común con este conjunto.

Encontrar la fórmula para $|A(n,k)|$

Escribí algunos ejemplos $|A(4,3)|=2$ Pero después de todo no puedo ver el patrón.

Gracias de antemano por la ayuda.

Answer 1

Oh, en realidad este es respondidas directamente por Frigyes del teorema.

El teorema se da una construcción de la $n$-gráfico de nodos, llamados el Frigyes gráfico de $T(n,k-1)$, que tiene el máximo número de aristas $B(n,k)$ bajo la restricción de que está libre de $k$-camarillas. Esto es equivalente a decir que a partir de $K_n$ tienes que eliminar (color) como muchos bordes como sea necesario para bajar a $T(n,k-1)$. La construcción es bastante fácil que usted debería ser capaz de averiguar $B(n,k)$ y, por tanto, $A(n,k) = {n \choose 2} - B(n,k)$.