Teoría de gráficos Pregunta - Triángulo y ángulo

Question

Me plantearon el siguiente problema y he resuelto el primero - pero no pude "deducir..." cualquier pista sería genial.

Demuestre que un gráfico completo con $2^t+1$ vértices no puede expresarse como la unión de $t$ grafos bipartitos. [ ] $2^t+1$ p al menos $(1-1/t)\pi$ radianes.

Answer 1

Si sólo quieres una pista, ve con esto:

Divide las aristas de tu gráfico completo por su pendiente, expresando así el gráfico como la unión de $t$ subgrafos, cada uno con aristas casi paralelas.

Si necesita más detalles, consulte el historial de revisiones.